为什么添加多态类型签名会降低性能？ [英] Why does adding a polymorphic type signature degrade performance?

问题描述

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

  fib :: [Int] 
 fib = 1： 1：zipWith（+）fib（尾纤）
  

在ghci中，我可以快速计算该系列。实际上，一些实验表明计算的运行时间大致是线性的。

  ghci> last $ take 100000 fib 
 354224848179261915075  - 花费不到一秒
  

如果我改变类型签名是多态的：

  fib :: Num a => [a] 
 fib = 1：1：zipWith（+）fib（尾纤）
  

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

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

解决方案

这是因为字典翻译。

  fib :: [Int] 
  

但这是：

  fib :: Num a => [a] 
 fib = 1：1：zipWith（+）fib（尾纤）
  

只是一个顶级函数，它将在运行时应用于 Num 字典。像这样：

  fib d = 1：1：zipWith（d。+）（fib d）（tail（fib d） ）
  

所以如果你没有进行任何优化就编译这个，这样就不会发生专门化，你会结束随着指数时间fib，因为列表从头开始重建，每次函数调用 - 它不再是一个懒惰的数据结构。

Here's a simple function to compute Fibonacci numbers:

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

In ghci I can compute the series quickly. In fact, a bit of experimentation reveals that the computation runs in approximately linear time.

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

If I change the type signature to be polymorphic instead:

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

Then the algorithm becomes slower. In fact, it seems that it now runs in exponential time!

Does switching to a polymorphic type signature mean that the list being completely recomputed at each stage? If so, why?

解决方案

This is because of the dictionary translation.

fib :: [Int]

is a top level constant.

But this:

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

is just a top level function, which will be applied to a Num dictionary at runtime. Like so:

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

So if you compile this without any optimizations, such that no specialization can happen, you'll end up with exponential time fib, as the list is rebuilt from scratch, on each function call -- it isn't a lazy data structure anymore.

这篇关于为什么添加多态类型签名会降低性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！