多型のシグネチャを追加するとパフォーマンスが低下するのはなぜですか？ここ

Question

は、フィボナッチ数を計算する簡単な関数です：GHCiの中

fib :: [Int] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

私はすぐにシリーズを計算することができます。実際、少しの実験では、計算がほぼ線形時間で実行されることがわかります。

ghci> last $ take 100000 fib 
354224848179261915075   -- takes under a second 

Iの代わりに多型であると型シグネチャを変更する場合：

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

アルゴリズムが遅くなります。実際には、指数関数的な時間で実行されているようです。

多型署名に切り替えると、リストが各段階で完全に再計算されますか？もしそうなら、なぜですか？

Answer 1

これは辞書の翻訳によるものです。

fib :: [Int] 

はトップレベルの定数です。

しかし、この：

fib :: Num a => [a] 
fib = 1 : 1 : zipWith (+) fib (tail fib) 

は、実行時にNum辞書に適用されるだけで、トップレベルの関数です。以下のようなので：あなたは何の専門は起こらないことができるような、任意の最適化せずにこれをコンパイルすると、リストは、各関数呼び出しに、ゼロから再構築されるよう

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d)) 

だから、あなたは、指数時間のFIBになってしまいます - これはもはや怠惰なデータ構造ではありません。

Answer 2

はい、多態型署名は、それが各段階で再計算されていることを意味します。 -O2でGHC-7.4.2によって生成されるコア：

lvl_rcZ :: GHC.Integer.Type.Integer 
[GblId, Str=DmdType] 
lvl_rcZ = __integer 1 

Rec { 
PolyFib.fib [Occ=LoopBreaker] 
    :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W] 
[GblId, Arity=1, Str=DmdType L] 
PolyFib.fib = 
    \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) -> 
    GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.List.zipWith 
      @ a_aal 
      @ a_aal 
      @ a_aal 
      (GHC.Num.+ @ a_aal $dNum_aam) 
      (PolyFib.fib @ a_aal $dNum_aam) 
      (case PolyFib.fib @ a_aal $dNum_aam of _ { 
       [] -> GHC.List.tail1 @ a_aal; 
       : _ xs_abD -> xs_abD 
      }))) 
end Rec } 

それが故に、その理由は、Numに属する各タイプのフィボナッチ数のリストをキャッシュすることは不可能だということです、そしてfibは明示的多型の値ですまったくキャッシュされません。

今リストで単相であるので、あなたは（そうpfibs !! 500などが速い）、各タイプで少なくとも計算のためにそれをキャッシュ

pfibs :: Num a => [a] 
pfibs = res 
    where 
    res = 1 : 1 : zipWith (+) res (tail res) 

は、各計算のキャッシングを行うローカルリストを使用したい場合各計算。単一のリスト要素ごとではなく、単一形の名前にバインドしない限り、各クエリに対してはまだ計算されます。

*PolyFib> pfibs !! 999999 :: Int 
-4249520595888827205 
(0.31 secs, 137462088 bytes)