42

以下のような無限リストの実行時のパフォーマンスに興味があります。

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

これにより、フィボナッチ数列の無限リストが作成されます。

私の質問は、次のことを行う場合です。

takeWhile (<5) fibs

fibsはリスト内の各用語を何回評価しますか? takeWhileリスト内の各項目の述語関数をチェックするため、リストfibsは各項を複数回評価するようです。最初の 2 タームは無料で提供されます。3 番目の要素takeWhileを評価 する場合は、次のようになります。(<5)

1 : 1 : zipWith (+) [(1, 1), (1)] => 1 : 1 : 3

ここで、一度4 番目の要素takeWhileを評価したい場合(<5): の再帰的な性質によりfibs、次のようにリストが再度構築されます。

1 : 1 : zipWith (+) [(1, 2), (2, 3)] => 1 : 1 : 3 : 5

4 番目の要素の値を評価するには、3 番目の要素を再度計算する必要があるようです。さらに、述語 intakeWhileが大きい場合は、関数がリスト内の前の各要素を複数回評価しているため、関数が必要なより多くの作業を行っていることを示します。ここでの私の分析は正しいですか、それともHaskellはここで複数の評価を防ぐためにキャッシュを行っていますか?

4

4 に答える 4

81

これは、構造の「後の」部分が名前で前の部分を参照する、自己参照型の遅延データ構造です。

最初は、構造体はそれ自体への未評価のポインターを使用した単なる計算です。展開されると、構造に値が作成されます。構造の計算済みの部分への後での参照は、それらを待っている値を見つけることができます。ピースを再評価する必要はなく、余分な作業も必要ありません!

メモリ内の構造は、評価されていないポインタとして始まります。最初の値を見ると、次のようになります。

> take 2 fibs

ここに画像の説明を入力

('1' を指すコンス セルへのポインター、および 2 番目の '1' を保持する末尾、および fibs への参照を保持する関数へのポインター、および fibs の末尾。

もう 1 つのステップを評価すると、構造が展開され、参照がスライドします。

ここに画像の説明を入力

そして、構造を展開し、毎回新しい未評価のテールを生成します。これは、最後のステップの 1 番目と 2 番目の要素への参照を保持するクロージャーです。このプロセスは無限に続く可能性があります:)

また、以前の値を名前で参照しているため、GHC は喜んでそれらをメモリに保持し、各項目は 1 回だけ評価されます。

于 2012-06-10T22:26:00.587 に答える
31

図：

module TraceFibs where

import Debug.Trace

fibs :: [Integer]
fibs = 0 : 1 : zipWith tadd fibs (tail fibs)
  where
    tadd x y = let s = x+y
               in trace ("Adding " ++ show x ++ " and " ++ show y
                                   ++ "to obtain " ++ show s)
                        s

生産する

*TraceFibs> fibs !! 5
Adding 0 and 1 to obtain 1
Adding 1 and 1 to obtain 2
Adding 1 and 2 to obtain 3
Adding 2 and 3 to obtain 5
5
*TraceFibs> fibs !! 5
5
*TraceFibs> fibs !! 6
Adding 3 and 5 to obtain 8
8
*TraceFibs> fibs !! 16
Adding 5 and 8 to obtain 13
Adding 8 and 13 to obtain 21
Adding 13 and 21 to obtain 34
Adding 21 and 34 to obtain 55
Adding 34 and 55 to obtain 89
Adding 55 and 89 to obtain 144
Adding 89 and 144 to obtain 233
Adding 144 and 233 to obtain 377
Adding 233 and 377 to obtain 610
Adding 377 and 610 to obtain 987
987
*TraceFibs>
于 2012-06-10T21:38:37.063 に答える
19

Haskell で何かが評価されると、同じ名前で参照されている限り、評価されたままになります1。

次のコードでは、リストlは 1 回だけ評価されます (これは明らかです)。

let l = [1..10]
print l
print l -- None of the elements of the list are recomputed

何かが部分的に評価されたとしても、その部分は評価されたままです:

let l = [1..10]
print $ take 5 l -- Evaluates l to [1, 2, 3, 4, 5, _]
print l          -- 1 to 5 is already evaluated; only evaluates 6..10

あなたの例では、fibsリストの要素が評価されると、評価されたままになります。引数zipWithは実際のfibsリストを参照するため、リスト内の次の要素を計算するときに、圧縮式が既に部分的に計算さfibsれたリストを使用することを意味します。これは、要素が 2 回評価されないことを意味します。

1もちろん、これは言語のセマンティクスによって厳密に要求されるわけではありませんが、実際には常にそうです。

于 2012-06-10T21:31:33.267 に答える
4

このように考えてください。変数fibは遅延値へのポインターです。(下にある遅延値は (実際の構文ではない) のようなデータ構造と考えることができますLazy a = IORef (Unevaluated (IO a) | Evaluated a)。つまり、サンクで評価されていないものとして開始します。その後、評価されると、値を記憶するものに「変化」します。)式は変数を使用fibし、同じ遅延値へのポインターを持ちます (データ構造を「共有」します)。誰かが を初めて評価するfibと、サンクを実行して値を取得し、その値が記憶されます。また、再帰式は同じ遅延データ構造を指しているため、それを評価すると、評価された値が既に表示されます。怠惰な「無限リスト」をトラバースするとき、メモリには「部分リスト」が 1 つだけ存在します。zipWith同じリストへのポインターで開始したため、同じ「リスト」の前のメンバーへのポインターである「リスト」への2つのポインターがあります。

これは実際には「メモ化」ではないことに注意してください。これは、同じ変数を参照した結果にすぎません。通常、関数結果の「メモ化」はありません (以下は非効率的です)。

fibs () = 0 : 1 : zipWith tadd (fibs ()) (tail (fibs ()))
于 2012-06-10T22:39:31.627 に答える