Haskell スクリプトのスペースが不足しています

Question

私はプロジェクト Euler を使用して Haskell を独学していますが、自分のコードが Haskell によってどのように実行されるかを推論するのに苦労しています。2 番目の問題では、400 万までのすべての偶数フィボナッチ数の合計を計算する必要があります。私のスクリプトは次のようになります。

fibs :: [Integer]
fibs =  1 : 2 : [ a+b | (a,b) <- zip fibs (tail fibs)]

evens  :: Integer -> Integer -> Integer
evens x sum | (even x)   = x + sum
            | otherwise  = sum

main = do
  print (foldr evens 0 (take 4000000 fibs))

Hugs では「ガベージ コレクションが十分なスペースを再利用できません」というエラーが表示されます。これは、リストのエントリが消費されるときに解放されないことを意味すると思います。 foldr.

これを修正するには何をする必要がありますか?アキュムレータを使用する末尾再帰 (だと思う) バージョンを作成しようとしましたが、それも機能しませんでした。

Answer 1

多数の観察/ヒント:

• の x + sum偶数は最後まで評価されない
• 4,000,000までの線維ではなく、最初の4,000,000の線維を摂取することになります。
• もっと簡単な方法があります

コメントに応じて編集する

何がより簡単な方法であるかについては説明しません。それがプロジェクト オイラーの問題の面白さだからです。しかし、私はあなたにたくさんの質問をします：

• 偶数の繊維を連続して何個持つことができますか?
• 均等な繊維なしでどのくらいの期間耐えることができますか?
• すべての偶数 Fib とすべての奇数 Fib を合計すると (これを手動で行います)、合計について何に気づきますか?

Answer 2

まず、あなたが抱擁を使用しないでください。それが唯一の教育目的のためにおもちゃです。

GHCは、しかし、Haskellのための高速、マルチコア対応最適化コンパイラです。 。特に、それは厳密な分析を行い、そしてネイティブコードにコンパイルされます。

あなたのコードについては際立っている主なものは、非常に大規模なリストのfoldrを使用することです。おそらくあなたは、末尾再帰ループをしたいです。これと同様ます：

import Data.List

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

evens x sum | even x    = x + sum
            | otherwise = sum

-- sum of even fibs in first 4M fibs
main = print (foldl' evens 0 (take 4000000 fibs))

それはしばらく時間がかかりますので、

すべてこのほか、最初の4MでものFIBは、スペースのかなりの量を使用します。

ここでの最初の400Kの合計は、さえのFIB に、保存するには、あなたのいくつかの時間（21S）。 ： - ）

Answer 3

あなたは問題を間違って理解しました。の 実際の問題 フィボナッチ数自体が 400 万を超えないように、偶数のフィボナッチ数をすべて合計してください (これはたまたま最初の 33 フィボナッチ数だけです)。

Answer 4

あなたはfibsの400万個の要素を評価しています。これらの数字は、指数関数的に成長します。私は万フィボナッチ数を表現するために必要とされるバイト数を知りません。ちょうど1000分の1のフィボナッチ数は211桁を持っているので、それは、単に数字を保持するための22の32ビット・ワードを取る課しオーバーヘッドどんなgmp気にしないだろう。そして、これらは、指数関数的に増大ます。

演習：。400万のフィボナッチ数を保持するために必要なメモリの量をcalculuate

Answer 5

でも、プレリュード機能takeWhile、フィルタを見て、その和

takeWhile（<40）[0 ..]
フィルタも、$ takeWhile（<40）[0 ..]

「日を一緒に入れます：

ANS =和$フィルタも$ takeWhile（<4×10 ^ 6）のFIB