ハスケルはこの膨大な数を即座にどのように計算しますか？

Question

私はハスケルを学び始めています。新しい言語を学んでいるときに好きなことの1つは、私の主な参考資料の補足として、Project Eulerの問題です。

私もフィボナッチ数未満400万の合計見つけるの第二の問題点を次のように解決策が出ている：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 
f :: Integer -> Integer 
f n = 
    let evenFib = filter (\n -> n `mod` 2 == 0) fibs 
    in sum (takeWhile (<n) evenFib) 

これは素晴らしい作品を、 f 4000000は正しい答えを返します。それはすぐにそうする。不思議なことに、私はもっと大きな数字を入力し始めました...

Prelude> f 40000000 
19544084 
Prelude> f 400000000000 
478361013020 
Prelude> f 40000000000000000000000000000000 
13049874051046942401006156573274 
Prelude> f 2370498572349582734598273495872349587234958723948752394857 
2805750129675962215536656398462489370528480907433875715844 

これらの値はそれぞれ直ちに返されます。私は最後の2つの答えの真実性を保証する方法がありません。なぜなら、私の他の言語での実装はこのような大きな数値に対しては機能しないからです。

私の質問は、ハスケルはここで何をしていますか？これらの値を瞬時に返す方法（実際に正しいかどうか）さらに、これらの答えは確かに正しいですか、またはハスケルはちょうどものを作っていますか？

Answer 1

特にハスケルとは関係ありませんが、他のソリューションで使用しているアルゴリズムです。

フィボナッチ数は非常に急速に成長したよう

（彼らは平均、各ステップの1.6倍大きくなり）、おそらくあまりこの未満の100の番号を追加するコンピュータ

100よりも、その多くのフィボナッチ数未満40000000000000000000000000000000ありませんサイズ（それほど大きくない）はマイクロ秒かかるはずです。 、

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

これはひどいです、fib nとして呼び出しfib (n-1)、その後、を呼び出します。

は、私はあなたの他の実装がどのように見えるかわからないんだけど、よくある間違いは、このようなフィボナッチ関数を書くことです答えはfib nに戻ります。しかし、答えを保存していないので、の計算をもう一度行う必要があります。

ハスケル（または実際に他の言語）でfibのより良い実装には、次のようなものです：各fib'呼び出しは一つだけ再帰すべてではなく、2になり

fib 0 = 0 
fib n = fib' 0 1 n 

fib' _ curr 1 = curr 
fib' last curr n = fib' curr (last+curr) (n-1) 

ていることに注意してください。私が上に書いたことは、おおよそ0 : 1 : zipWith (+) fibs (tail fibs)がやっていることですが、上記のコードはちょっと混乱していますが、おそらく他の言語にも簡単に翻訳できます。

Answer 2

回答が正しいはずです。

:set +s ghciプリントメモリ/時刻情報を作成することができます。もう一度テストを実行

、あなたはそれが実際にはより多くのメモリを使用していていることがわかります。

Prelude> :set +s 
Prelude> :{ 
Prelude| fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 
Prelude| f :: Integer -> Integer 
Prelude| f n = 
Prelude| let evenFib = filter (\n -> n `mod` 2 == 0) fibs 
Prelude| in sum (takeWhile (<n) evenFib) 
Prelude| :} 
(0.14 secs, 0 bytes) 
Prelude> f 40000000 
19544084 
(0.02 secs, 83,440 bytes) 
Prelude> f 40000000 
19544084 
(0.01 secs, 83,200 bytes) 
Prelude> f 400000000000 
478361013020 
(0.01 secs, 94,800 bytes) 
Prelude> f 40000000000000000000000000000000 
13049874051046942401006156573274 
(0.01 secs, 149,400 bytes) 
Prelude> f 2370498572349582734598273495872349587234958723948752394857 
2805750129675962215536656398462489370528480907433875715844 
(0.01 secs, 225,488 bytes) 

をそして、それはevenFib

Prelude> sequence_ $ map (putStrLn . show) $ take 20 $ filter ((== 0) . (flip mod 2)) $ fibs 
0 
2 
8 
34 
144 
610 
2584 
10946 
46368 
196418 
832040 
3524578 
14930352 
63245986 
267914296 
1134903170 
4807526976 
20365011074 
86267571272 
365435296162 
(0.02 secs, 203,472 bytes) 

の開始時に見て、非常に高速だ理由を理解します

番号はというように成長しています。

Answer 3

他の回答に記載されているとおり、かなり簡単です。それはすでに速いですが、私はまだ怠惰に頼ってより効率的なアプローチを持っています。

フィボナッチシリーズを作成するなどの仕事については、私はunfoldrが理想的なツールであると信じて、結果を得るためにはfoldr1を使用するだけです。この例では、foldr1は、takeWhileとfilterの機能を実装し、同じ作業を1回のパスで実行します。だから、怠惰な展開と折りたたみ、O（n）のみ。

fibs :: [Integer] 
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1) 

sumEvenFibsUpto :: Integer -> Integer 
sumEvenFibsUpto n = foldr1 (\ x y -> if x < n then if x `rem` 2 == 0 then x + y 
                     else y 
               else 0) fibs 

*Main> sumEvenFibsUpto 2370498572349582734598273495872349587234958723948752394857 
2805750129675962215536656398462489370528480907433875715844 
(0.01 secs, 324,392 bytes)