为什么更通用的类型会影响Haskell中的运行时？

Question

考虑以下两个无限斐波纳契数列的实现:

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

fibsB :: [Integer]
fibsB = 0:1:(zipWith (+) fibsB (tail fibsB))

在GHCI中,执行fibsB !! k比执行快得多fibsA !! k.特别是,似乎fibsA不断重新计算值(不记忆/存储).

此外,当省略类型签名时,GHCI :t显示它[Integer],并且该功能相应地执行.

在编译的代码(ghc -O3 Fibs.hs)中也会发生此行为.

为什么它Integer比这快得多Num a => a？

Answer 1

在编写时fibsA :: Num a => [a],编译器构造本质上是什么

fibsA :: NumDict a -> [a]

哪里

data NumDict a = NumDict
    { (+)         :: a -> a -> a
    , (-)         :: a -> a -> a
    , (*)         :: a -> a -> a
    , negate      :: a -> a
    , abs         :: a -> a
    , signum      :: a -> a
    , fromInteger :: Integer -> a
    }

请注意,Num a已从约束转变为函数的参数. 类型类本质上只是实现该类的每种类型的查找表.因此Num,默认情况下你会有

mkInteger_NumDict :: NumDict Integer
mkInteger_NumDict = NumDict
    { (+) = integer_plus
    , (-) = integer_minus
    , (*) = integer_mult
    , ...
    }

mkInt_NumDict     :: NumDict Int

mkFloat_NumDict   :: NumDict Float

mkDouble_NumDict  :: NumDict Double

当解析实例时,这些会自动传递给使用类型类的函数.这意味着我们的函数fibsA本质上是一个参数.当你从GHCi调用它时,默认规则会启动并选择Integer,但是由于它是以这种方式调用的,所以内部看起来更像这样:

{-# RecordWildCards #-}  -- To reduce typing

fibsA :: NumDict a -> [a]
fibsA nd@(NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) (fibsA nd) (tail $ fibsA nd)

你看到这个问题了吗？它仍然是递归的,但现在它必须在每个步骤中调用函数,从而降低性能.如果你想让它变得非常快,那么聪明的程序员就可以做到

fibsA nd@(NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) fibsA' (tail fibsA')
    where fibsA' = fibsA nd

这至少允许记忆.但是,haskell二进制文件无法在运行时真正执行此优化,这在编译时发生.所以你最终得到的是一个较慢的递归函数.有了fibsB,你具体指定了类型,它的类型签名没有多态约束.该值fibsB没有隐式或显式参数,因此当引用它时,它是指向内存中同一对象的指针. fibsA是一个指向函数的指针,因此当递归使用时,它会返回内存中的新对象,并且没有memoization.这就是为什么fibsB速度快fibsA,只是fibsB得到优化,因为编译器不必让它Num只为所有人工作Integer.

Answer 2

除了@ bheklilr的详尽解释:你还可以fibsA快速,如果你在函数内部执行列表共享,使其非递归(隐藏递归内部):

fibsA' :: Num a => [a]
fibsA' = 
  let f = 0:1:(zipWith (+) f (tail f))
  in f