非pointfreeスタイルは実質的に遅いです

Question

I持っHaskellでn番目のフィボナッチ数を計算するために、以下の、しばしば引用符で囲まれたコード：

ghci> fibonacci 1000 

：

fibonacci :: Int -> Integer 
fibonacci = (map fib [0..] !!) 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

は、私のような呼び出しを行うことができ、これを使用します

とほぼ瞬時に回答が届きます。それは、pointfreeスタイルではないように私は上記のコードを変更した場合

しかし、すなわち

fibonacci :: Int -> Integer 
fibonacci x = (map fib [0..] !!) x 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

それは実質的に遅いです。

ghci> fibonacci 1000 

などのコールがハングする程度まで。

私の理解では、上記の2つのコードは同等でしたが、GHCiは異なっています。誰もこの行動の説明を持っていますか？

Answer 1

違いを確認するには、おそらくコアを参照する必要があります。私の推測で、これは（おおよそ）を比較するに

let f = map fib [0..] in \x -> f !! x 

\x -> let f = map fib [0..] in f !! x 

に沸くこと、後者は、すべての呼び出しでゼロからfを再計算します。前者は、呼び出しごとに同じfを効果的にキャッシュしません。

この特定のケースでは、最適化が有効になってからGHCが最初のものに最初のものを最適化することができました。

ただし、GHCは必ずしもこの変換を実行するわけではありませんが、これは必ずしも最適化ではないためです。最初に使用されたキャッシュは永遠にメモリに保持されます。これは、手元の機能に応じて、メモリの浪費につながる可能性があります。

Answer 2

私はそれを見つけようとしましたが、打ち明けました。私は自宅のPCでそれを持っていると思う。 私が読んだのは、固定小数点を使用する関数が本質的に高速だったということでした。 固定小数点を使用する理由は他にもあります。私はこの反復フィボナッチ関数を書く際に遭遇しました。私は反復的なバージョンがどのように実行されるのかを見たいと思っていました。私はハスケル新生児です。しかし、ここでテストする人のための反復バージョンです。 最初の最後の機能の後にドットを使用しない限り、これを定義することはできませんでした。 私はさらにそれを減らすことができませんでした。 [0,1]パラメータは固定であり、パラメータ値として供給されない。

Prelude> fib = last . flip take (iterate (\ls -> ls ++ [last ls + last (init ls)]) [0,1]) 
Prelude> fib 25 

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025]