9

私は Haskell を学んでいますが、Haskell Wikiの次の式に は本当に戸惑いました。

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

なぜこれが機能するのか、私にはよくわかりません。

標準のカリー化ロジックを適用する(zipWith (+))と、引数としてリストを受け取る関数が返され、別のリストを引数として受け取る別の関数が返され、リスト ( zipWith::(a -> b -> c) -> [a] -> [b] -> [c]) が返されます。したがって、fibsは (まだ評価されていない) リストへの参照(tail fibs)であり、同じ (未評価の) リストの末尾です。( ) を評価しようとするとtake 10 fibs、最初の 2 つの要素が と にバインドされ0ます1。つまりfibs==[0,1,?,?...]、 と(tail fibs)==[1,?,?,?]. 最初の追加が完了すると、 にfibsなり[0,1,0+1,?,..]ます。同様に、2 番目の加算の後、次のようになります。[0,1,0+1,1+(0+1),?,?..]

  • 私の論理は正しいですか？
  • これを説明する簡単な方法はありますか？(Haskell コンパイラがこのコードで何をするかを知っている人からの洞察はありますか?) (リンクと参照は大歓迎です)
  • このタイプのコードは、遅延評価のためにのみ機能するというのは本当ですか?
  • を行うと、どのような評価が行われますfibs !! 4か?
  • このコードは、zipWith が要素を最初から最後まで処理することを前提としていますか? （そうすべきではないと思いますが、理由がわかりません）

EDIT2：上記の質問があり、ここでよく答えられていることがわかりました。誰かの時間を無駄にしてしまい申し訳ありません。

編集: これは理解するのがより難しいケースです (ソース: Project Euler forums ):

filterAbort :: (a -> Bool) -> [a] -> [a]
filterAbort p (x:xs) = if p x then x : filterAbort p xs else []

main :: Int
main = primelist !! 10000
         where primelist = 2 : 3 : 5 : [ x | x <- [7..], odd x, all (\y -> x `mod` y /= 0) (filterAbort (<= (ceiling (sqrt (fromIntegral x)))) primelist) ]

ここでall (\y -> x mod y /= 0)... x を参照しても無限再帰が発生しないことに注意してください。

4

1 に答える 1

16

私はあなたのために評価をたどります：

> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

と：

> zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
> zipWith _ _      _      = []

> tail (_:xs)             =  xs
> tail []                 =  error "tail"

そう：

  fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
↪ fibs = 0 : 1 : ((+) 0 1 : zipWith (+) (tail fibs) (tail (tail fibs)))
↪ fibs = 0 : 1 : 1 : ((+) 1 1 : zipWith (+) (tail (tail fibs)) (taii (tail (tail fibs)))))    
↪ fibs = 0 : 1 : 1 : 2 : ((+) 1 2 : zipWith (+) (tail (tail (tail fibs))) (tail (taii (tail (tail fibs))))))
↪ fibs = 0 : 1 : 1 : 2 : 3 : ((+) 2 3 : zipWith (+) (tail (tail (tail (tail fibs)))) (tail (tail (taii (tail (tail fibs)))))))

そのため、この構造にインデックスを付けると、インデックスが見つかるまで fibs の各ステップが強制的に評価されます。

なぜこれが効率的なのですか？一言：共有。

計算されるとfibs、ヒープ内で成長し、計算された値が記録されます。fibsの以前に計算されたすべての値を再利用するために後で参照しますfibs。無料のメモ化！

その共有はヒープでどのように見えるでしょうか?

ここに画像の説明を入力

リストの最後にあるオブジェクトを要求すると、Haskell は次の値を計算して記録し、その自己参照をノードの下に移動します。

これが終了するという事実は、怠惰に大きく依存しています。

于 2011-06-16T00:17:51.723 に答える