GHC如何知道如何缓存一个函数而不是其他函数？

Question

我读你学习哈斯克尔(到目前为止爱它),并教导如何实现elem来讲foldl,使用Lambda.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 Land教给我的一个术语)elem3而不是另外两个？

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首先如此,如果由于懒惰你不评估第一个操作数,你仍然需要迭代到列表的末尾.

如果我们实现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是,您不会懒惰地执行唯一性:您首先将所有元素提取到列表中,因此,您将再次遍历所有元素,而不是在第一次点击后切断搜索.

Answer 2

说明

foldl 转到列表的最内层元素,应用计算,并再次递归到结果和列表的下一个最内层值,依此类推.

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

因此,为了产生结果,它必须遍历所有列表.

相反,在你的函数中,elem3因为一切都是懒惰的,所以在你打电话之前根本没有计算任何东西head.

但是为了计算这个值,你只是(过滤的)列表的第一个值,所以你只需要3在你的大列表中遇到.这很快,所以列表没有遍历.如果你要求1000000th元素,eleme3可能会像其他元素一样糟糕.

Lazyness

懒惰确保您的语言始终是可组合的:将函数分解为子函数不会改变所做的事情.

您所看到的可能导致空间泄漏,这实际上是关于控制流如何以惰性语言工作.无论是严格还是懒惰,您的代码都将决定评估的内容,但具有微妙的差异:

• 在严格的语言中,函数的构造者将选择,因为它强制评估其参数:任何被调用的人都负责.

• 在懒惰的语言中,函数的消费者选择.谁打电话谁负责.它可以选择仅评估第一个元素(通过调用head)或每个其他元素.所有这一切提供其自己的来电者选择,以评估自己的计算也是如此.有一整套指挥决定做什么.

在那个阅读中,你的foldl基础elem函数以一种必不可少的方式使用"控制反转":elem被要求产生一个值.foldl深入到列表中.如果第一个元素,y那么它返回平凡的计算True.如果不是,它将请求转发 给计算 acc.换句话说,你读的价值acc,x甚至True,真的是占位符的计算,你接受和产量回来.事实上,acc可能是一些令人难以置信的复杂计算(或者说是不同的计算undefined),只要你将控制转移到计算中True,你的调用者就永远不会看到它的存在acc.

foldr vs foldl vs foldl'VS speed

正如在另一个答案中所建议的那样,折叠器可能最好的你如何遍历列表的意图,并将屏蔽你远离空间泄漏(而如果你真的想要穿越另一种方式,折叠'将防止空间泄漏,这可能导致复杂计算的积累...... 例如,对循环计算非常有用).

但速度问题实际上是算法问题.当且仅当您事先知道您具有某种使用模式时,集合成员资格可能有更好的数据结构.

例如,支付一些前期成本Set,然后拥有快速的成员资格查询可能是有用的,但这只有在您知道您将拥有这样一种模式的情况下才有用,其中您有几个集合并且对这些集合有大量查询.其他数据结构对于其他模式是最佳的,并且值得注意的是,从API /规范/接口的角度来看,它们通常与消费者相同.这是任何语言中的一般现象,以及为什么许多人喜欢编程中的抽象数据类型 /模块.

使用foldr并期望更快的实际编码假设,鉴于您对未来访问模式的静态知识,您可能会测试成员身份的值将位于开头.foldl如果你期望你的价值在它的末尾,那么使用会很好.

请注意,使用foldl,您可以构造整个列表,您不需要自己构造值,直到您需要它为止,例如测试相等性,只要您没有找到搜索到的元素.