在Haskell中,性能和绑定

Question

我正在学习Haskell并从教程网站编写了两个程序

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绑定会产生巨大的性能差异,但我不知道为什么.有谁可以帮我解释一下？

Answer 1

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

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

故事的寓意是,如果你想要分享,你需要通过使用let或者提出要求where.