15

这是一个计算斐波那契数的简单函数：

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

在 ghci 中，我可以快速计算系列。事实上，一些实验表明计算运行在近似线性的时间内。

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

如果我将类型签名更改为多态：

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

然后算法变得更慢。事实上，它现在似乎以指数时间运行！

切换到多态类型签名是否意味着列表在每个阶段都被完全重新计算？如果是这样，为什么？

4

2 回答 2

15

是的，多态类型签名意味着它在每个阶段都被重新计算。ghc-7.4.2 产生的核心-O2：

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 :: Num a => [a]
pfibs = res
  where
    res = 1 : 1 : zipWith (+) res (tail res)

为每个计算进行缓存（pfibs !! 500例如很快），因为现在列表在每个计算中都是单态的。它仍然会为每个查询重新计算（除非您将它绑定到一个单态名称），但不会为每个单个列表元素重新计算。

*PolyFib> pfibs !! 999999 :: Int
-4249520595888827205
(0.31 secs, 137462088 bytes)
于 2012-06-21T19:54:23.283 回答
15

这是因为字典翻译。

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，因为列表是在每次函数调用时从头开始重建的——它不再是一个惰性数据结构。

于 2012-06-21T20:02:48.987 回答