GHC如何区分哪些函数需要缓存，哪些不需要？

Question

我正在阅读《Learn You a Haskell》（迄今为止非常喜欢），它教我们如何使用lambda和foldl实现elem。然而，使用lambda的解决方案对我来说有些丑陋，因此我尝试想出另一种实现方式（全部使用foldl）：

import qualified Data.Set as Set
import qualified Data.List as List

-- LYAH implementation
elem1 :: (Eq a) => a -> [a] -> Bool
y `elem1` ys = 
    foldl (\acc x -> if x == y then True else acc) False ys

-- When I thought about stripping duplicates from a list
-- the first thing that came to my mind was the mathematical set
elem2 :: (Eq a) => a -> [a] -> Bool
y `elem2` ys = 
    head $ Set.toList $ Set.fromList $ filter (==True) $ map (==y) ys

-- Then I discovered `nub` which seems to be highly optimized: 
elem3 :: (Eq a) => a -> [a] -> Bool
y `elem3` ys = 
    head $ List.nub $ filter (==True) $ map (==y) ys

我在 GHCi 中加载了这些函数并执行了 :set +s，然后进行了一个小型基准测试：

3 `elem1` [1..1000000] --  => (0.24 secs, 160,075,192 bytes)
3 `elem2` [1..1000000] --  => (0.51 secs, 168,078,424 bytes)
3 `elem3` [1..1000000] --  => (0.01 secs, 77,272 bytes)

然后我尝试在一个（远远）更大的列表上执行同样的操作：

3 `elem3` [1..10000000000000000000000000000000000000000000000000000000000000000000000000]

elem1和elem2花费了很长时间，而elem3瞬间完成（几乎与第一个基准测试相同）。我认为这是因为GHC知道3是[1..1000000]的成员，而我在第二个基准测试中使用的大数字比1000000还要大，因此3也是[1..bigNumber]的成员，GHC根本不需要计算表达式。
但是，它如何能够自动缓存（或记忆化，一种Lisp之地教给我的术语）elem3而不是另外两个？

- ohmree

---

你会注意到，当 y 变得越大时，elem3 变得越来越慢，而 ys 保持不变。 - chepner

Answer 1

简短回答：这与缓存无关，而是因为在前两个实现中你强制使用了Haskell来迭代所有元素。

不，这是因为foldl从左到右工作，但它会一直迭代列表直到列表耗尽。

因此，最好使用foldr。从它在列表中找到3的那一刻起，它将停止搜索。

这是因为foldr被定义为：

foldr f z [x1, x2, x3] = f x1 (f x2 (f x3 z))

而 foldl 实现为：

foldl f z [x1, x2, x3] = f (f (f (f z) x1) x2) x3

请注意，外部的f与x3绑定在一起，这意味着如果由于惰性求值而不评估第一个操作数，您仍然需要迭代到列表的末尾。如果我们实现foldl和foldr版本，我们会得到:

y `elem1l` ys = foldl (\acc x -> if x == y then True else acc) False ys
y `elem1r` ys = foldr (\x acc -> if x == y then True else acc) False ys

我们接下来得到：

Prelude> 3 `elem1l` [1..1000000]
True
(0.25 secs, 112,067,000 bytes)
Prelude> 3 `elem1r` [1..1000000]
True
(0.03 secs, 68,128 bytes)

从列表中剔除重复项不会提高效率。而提高效率的是您使用map。 map按从左到右的顺序进行操作。此外请注意，nub可以惰性操作，因此在这里nub不会对性能造成影响，因为您只关注头部，所以Haskell不需要在已经看过的元素上执行成员检查。

两种方法的性能几乎相同：

Prelude List> 3 `elem3` [1..1000000]
True
(0.03 secs, 68,296 bytes)

如果您使用Set，则不会惰性执行唯一性：您首先将所有元素提取到列表中，因此再次迭代所有元素，并且在第一次命中后不会停止搜索。

- Willem Van Onsem

Answer 2

说明

foldl从列表的最内层元素开始，应用计算，然后递归地对结果和列表中下一个最内层的值再次执行相同的操作，以此类推。

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

为了得到结果，它必须遍历整个列表。

相反，在您的函数elem3中，由于所有内容都是惰性的，直到调用head之前不会计算任何内容。

但是为了计算该值，您只需获取（过滤后的）列表的第一个值，因此您只需要一直走到在大列表中遇到3。这很快，所以列表没有被遍历。如果您要求第1000000th个元素，则eleme3可能像其他函数一样表现糟糕。

懒惰确保您的语言始终可组合：将函数分解为子函数不会改变所执行的操作。

您所看到的可能会导致空间泄漏，这实际上与惰性语言中控制流如何工作有关。在严格和惰性中，您的代码将决定何时进行评估，但存在微妙的差异：

• 在严格语言中，函数的构建者将会选择强制评估其参数的方式：由谁调用就由谁来负责。

• 在惰性语言中，使用者将会选择。由调用者来决定。它可以选择仅评估第一个元素（通过调用head），或每隔一个元素进行评估。只要自己的调用者也选择评估自己的计算。有一整个命令链决定要做什么。

在这个阅读中，基于foldl的elem函数以一种关键的方式使用了“控制反转”： elem被要求产生一个值。 foldl深入列表中。如果第一个元素为y，则返回平凡的计算True。如果不是，则将请求转发给计算acc。换句话说，您所读到的acc、x甚至True等值实际上是计算的占位符，您会接收并返回它们。事实上，acc可能是一些难以置信的复杂计算（或者像undefined这样的发散计算），只要您将控制传递给计算True，您的调用者就永远看不到acc的存在。

foldr vs foldl vs foldl' VS speed

正如另一个答案所建议的那样，foldr可能是最适合您遍历列表的方式，并且将使您远离空间泄漏（而foldl'也可以防止空间泄漏，如果您真的想要朝另一边遍历，这可能会导致复杂计算的积累...并且对于circular computation非常有用）。

但是速度问题确实是算法问题。如果您事先知道您具有某种使用模式，则可能存在更好的数据结构用于集合成员身份验证。

例如，支付一些前期成本以获得Set，然后进行快速成员资格查询可能很有用，但仅在您知道您将拥有此类模式的情况下才有用，其中您有少量集合和大量查询这些集合。其他数据结构对于其他模式是最优的，有趣的是从API /规范/接口的角度来看，它们通常对于消费者来说是相同的。这是任何语言中的一般现象，也是为什么许多人喜欢编程中的抽象数据类型/模块的原因。

使用 foldr 并期望它更快，实际上是假设您对未来访问模式的静态了解，您可能会测试成员资格的值将位于开头。如果您希望值在其末尾，则使用 foldl 也可以。请注意，使用 foldl，您可能会构建整个列表，直到您需要它为止，例如为了测试相等性，只要您还没有找到所搜索的元素，就不会构造值本身。

- nicolas