为什么更通用的类型会影响Haskell中的运行时？ [英] Why does a more general type affect runtime in Haskell?

问题描述

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

  fibsA :: Num a => [a] 
 fibsA = 0：1 :( zipWith（+）fibsA（tail fibsA））
 
 fibsB :: [Integer] 
 fibsB = 0：1 :( zipWith （+）fibsB（tail fibsB））
  

在GHCI中，执行 fibsB！ ！ k 比执行 fibsA !!快得多！ ķ。
特别是， fibsA 的值似乎会不断重新计算（不会被记忆/存储）。

<此外，当省略类型签名时，GHCI的：t 表明它是 [Integer] ，而函数执行相应的操作。

编译后的代码中也会出现这种情况（ ghc -O3 Fibs.hs ）。 p>

为什么整数比要快得多？Num a => a ？

解决方案当您编写 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 ，您会默认使用

pre $ m $ c $ m $ mkInteger_NumDict :: NumDict Integer
mkInteger_NumDict = NumDict
{（+）= integer_plus
，（ - ）= integer_minus
，（*）= integer_mult
，...
}

mkInt_NumDict :: NumDict Int

mkFloat_NumDict :: NumDict浮点数

mkDouble_NumDict :: NumDict Double

并且这些会在解析实例时自动传递给一个使用类型类型的函数。这意味着我们的函数 fibsA 本质上是一个参数。当你从GHCi中调用它时，违约规则会启动并选择 Integer ，但由于它被这样调用，所以它在内部看起来更像这样：

  { - ＃RecordWildCards＃ - }  - 减少键入
 
 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'= fibsAnd

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

Consider the two following implementations of an infinite Fibonacci sequence:

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

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

In GHCI, executing fibsB !! k is much faster than executing fibsA !! k. In particular, it seems that the values of fibsA are continuously recalculated (not memoized/stored).

Furthermore, when the type signature is omitted, GHCI's :t shows it to be [Integer], and the function performs accordingly.

This behavior also occurs in compiled code (ghc -O3 Fibs.hs).

Why is it the case that Integer is so much faster than Num a => a?

解决方案

When you write fibsA :: Num a => [a], the compiler constructs what is essentially

fibsA :: NumDict a -> [a]

Where

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
    }

Notice that Num a has moved from being a constraint to being an argument to the function. A typeclass is essentially just a lookup table for each type that implements the class. So for Num, you'd have by default

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

and these get automatically passed to a function using a typeclass when the instance is resolved. This means that our function fibsA essentially takes an argument. When you call it from GHCi, the defaulting rules kick in and pick Integer, but since it's being called this way it would look more like this internally:

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

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

Do you see the problem with this? It's still recursive, but now it has to make a function call each step of the way, reducing performance. If you wanted to make it really fast, a smart programmer would do

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

This at least allows memoization. However, a haskell binary can't really perform this optimization at runtime, that happens at compile time. So what you end up with is a slower recursive function. With fibsB, you're specifying the type concretely, there are no polymorphic constraints on it's type signature. The value fibsB has no implicit or explicit arguments, so when referred to it's a pointer to the same object in memory. fibsA is a pointer to a function, so when used recursively it returns new objects in memory, and has no memoization. This is why fibsB is faster than fibsA, only fibsB gets optimized because the compiler doesn't have to make it work for all Num, only Integer.

这篇关于为什么更通用的类型会影响Haskell中的运行时？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！