3

Project Eulerの問題2を解決するためにGHCiを使用しています。
http://projecteuler.net/problem=2

無限リスト fib を次のように定義しました。

Prelude> let fibs = 1 : 2 : zipWith(+) fibs (テールフィブ)

次の方法でリスト内包表記を使用してみました。

プレリュード> [x | x<-fibs、x mod2 == 0、x<4000000] [1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657, 46368、75025、121393、196418、317811、514229、832040、1346269、2178309、3524578
_ x <- [1..], x mod2 == 0, x<4000000]

しかし、シェルは 2 番目のコマンドでハングします。リスト内包表記がリストを作成できるのに、合計関数がそれを処理できない理由について、私は混乱しています。

私は実用的な解決策が

Prelude> sum $ filter even $ takeWhile (<= 4000000) fibs

しかし、リスト内包表記法が機能しないのに、なぜそれが機能するのかについて、私は再び混乱しています。

4

3 に答える 3

14

評価時

[x | x<-fibs, x mod 2 == 0, x<4000000]

あなたのプログラム/Haskell コンパイラは、このリストが実際に有限であることを知りません。のようなリストを完全に消費する関数を呼び出すと、sumフィボナッチ数を生成し続け、それらをテストしますx<4000000(そして、特定のポイントの後に毎回失敗します)。

実際、Haskell コンパイラは、一般的なケースでは、内包表記が有限リストを表しているかどうかを知ることができません。問題は判断不能です。

于 2012-07-09T23:19:35.547 に答える
1

最初のコマンドでもハングしますね。:)

テストを使用したリスト内包表記は、filter式ではなく式と同等takeWhileです。

sum $ [x | x <- [1..], x mod 2 == 0, x<4000000] ===

sum $ filter (<4000000) $ filter even $ [1..]

これは、非終了の計算を明確に説明しています。

Haskellの内包表記には、Prologのカット（つまり「！」）に相当するものはありません。Prologでは、「テスト内から」計算を停止することができます。

sum(I,Acc,Res):- I >= 4000000, !, Res = Acc ;
  Acc2 is Acc+I, sum(I+1,Acc2,Res).

しかし、HaskelltakeWhileでは、またはを使用してカットをエミュレートする必要がありtakeます。

于 2012-07-10T09:58:08.367 に答える
0

に置き換える[1..]とfibs、2 番目のバリアントは最初のバリアントと同等になります。

編集：申し訳ありませんが、そうではありません。しかし、間違いは「少ない」でしょう :) もっと注意を払う必要があります…</p>

于 2012-07-09T23:18:16.763 に答える