在Haskell中，性能和约束力 [英] In Haskell, performance and where binding

问题描述

我正在学习Haskell，并从一个教程站点编写了两个程序，例如

I am just learning Haskell and wrote two programs from a tutorial site, such that

maximumnowhere :: (Ord a) => [a] -> a
maximumnowhere [] = error "empty"
maximumnowhere [x] = x
maximumnowhere (x:xs) = if x > maximumnowhere xs then x else maximumnowhere xs

和

maximumwhere :: (Ord a) => [a] -> a
maximumwhere [] = error "empty"
maximumwhere [x] = x
maximumwhere (x:xs) = if x > maximum' then x else maximum' where maximum' = maximumwhere xs

我认为这两个程序相当等效，因为我认为，where绑定仅将变量替换为其内容.但是当我在ghci中运行它时，第一个要比后者慢得多，尤其是对于长度超过25的数组.也许，where绑定会产生巨大的性能差异，但是我不知道为什么.谁能为我解释一下?

I thought these two programs are fairly equivalent, cause I thought, the where binding only replaces the variable with its content. but when I run it in ghci, the first one was way slower than the latter, especially for an array with length over 25. Probably, the where binding makes this huge performance difference, but I don't know why. Can anyone explain it for me?

推荐答案

不，它们不是等效的. let和where引入了共享，这意味着该值仅被评估一次.除非您告诉编译器，否则编译器通常不会共享两个相同表达式的结果，因为编译器通常无法自行判断这样做的时空权衡是否有益.

No, they are not equivalent. let and where introduce sharing, which means that the value is only evaluated once. The compiler will in general not share the result of two identical expressions unless you tell it to, because it cannot in general tell on its own whether the space-time trade-off of doing this is beneficial or not.

因此，您的第一个程序每次迭代将进行两次递归调用，使其为 O(2 ^ n)，而第二个程序每次迭代仅进行一次递归调用，即 O(n).这些之间的差异是巨大的.在 n = 25 时，第一个程序导致超过3,300万次递归调用，而第二个程序仅进行25次.

Thus, your first program will do two recursive calls per iteration, making it O(2^n), while the second only does one per iteration, i.e. O(n). The difference between these is huge. At n = 25, the first program results in over 33 million recursive calls while the second only does 25.

所以故事的寓意是，如果您要共享，则需要使用let或where来请求.

So the moral of the story is that if you want sharing, you need to ask for it by using let or where.

这篇关于在Haskell中，性能和约束力的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！