haskell - 在 Haskell 中，性能和绑定(bind)

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 绑定(bind)仅用变量的内容替换变量。但是当我在 ghci 中运行它时，第一个比后者慢得多，特别是对于长度超过 25 的数组。可能是 where 绑定(bind)造成了巨大的性能差异，但我不知道为什么。谁能为我解释一下吗？

Answer 1

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

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

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