14

私はHaskellを（非常に良い意味で）学ぼうとしています。私が行っているさまざまなことの1つは、自分の気力をテストするために、プロジェクトオイラーの問題に取り組んでいることです。

フィボナッチベースの問題のいくつかを実行する際に、私はつまずいて、フィボナッチ数列の再帰的な無限リストバージョンをいじり始めました。

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

PEの問題の1つとして、4,000,000未満のフィボナッチ数のサブシーケンスを抽出する必要がありました。私はこれをリスト内包表記で行うことにしました。コードをいじってみると、よくわからないことがわかりました。物事を複雑にしているのは、Haskellの遅延評価スキームに対する私の弱い理解だと思います。

次の理解は問題なく機能します。

[x | x <- takeWhile (<= 4000000) fibs, even x]

次の理解は永遠に回転します。それで、私は調べて、出力をstdoutに戻しました。それが正しい場所で停止している間、上限値に達した後、終了せずに再帰的に定義されたリストを永遠に評価し続けるようです。リストの最後の項目がコンマで印刷されているが、それ以上のリスト項目または閉じ角括弧が存在しないという事実を示します。

[x | x <- fibs, x <= 4000000, even x]

では、無限のリストでうまく機能するさまざまな関数で使用される秘密のソースは正確には何ですか？

4

1 に答える 1

24

この関数は、述語を満たさないtakeWhile最初の要素に到達するまで入力リストの要素を取得し続け、その後停止します。述語を満たさない要素が少なくとも 1 つある限り、無限リストを有限リストに変換します。takeWhile

あなたの最初の表現は言う

4,000,000 を超える要素が見つかるまで、この無限リストの要素を取得し続け、その後停止します。偶数の場合、各要素を出力に含めます。

2番目の表現は言う

この無限リストの要素を取り続けます。各要素が 4,000,000 以下で偶数の場合、出力に含めます。

出力が永久に停止するのを観察すると、関数はビジー状態でより多くのフィボナッチ数を生成し、それらが 4,000,000 以下かどうかを確認しています。どれもそうではありません。そのため、画面には何も表示されませんが、関数は、リストの少し下にある小さな数に遭遇しないことを知る方法がないため、チェックを続ける必要があります。

于 2012-11-12T16:33:02.830 に答える