为什么`foldl1`内存不足但'foldr1`工作正常？

Question

我last用foldl1和编写函数foldr1.

lastr :: [a] -> a
lastr = foldr1 (flip const)

lastl :: [a] -> a
lastl = foldl1 (flip const)

它们只适用于短名单.但是当我尝试使用很长的列表[1..10 ^ 8]时,lastr在6.94秒内返回解决方案但是lastl内存不足.

foldr1和foldl1的定义是(根据我的理解)

foldr1 f [x] = x
foldr1 f (x:xs) = f x $ foldr1 f xs

和

foldl1 f [x] = x
foldl1 f (x:y:ys)=foldl1 f $ f x y : ys

从这些看来,foldl1似乎比foldr1使用更少的内存,因为foldr1需要保持一个表达式f x1 $ f x2 $ f x3 $ f x4 $...,因为foldl1可以只计算f x y每次并将其存储为列表的头元素而不是保持它直到它达到10 ^ 8.

谁能告诉我我的论点有什么问题？

Answer 1

如果组合函数在其第二个参数中是惰性的,则右侧折叠可以立即开始生成.一个简单的例子:

foldr1 (++) ["one", "two", "three", ...]
    ~> "one" ++ foldr1 (++) ["two", "three", ...]

并且可以立即访问结果的第一部分而无需进一步评估第二个参数(++).只需在消耗第一部分时评估.通常,第一部分可能已经被垃圾收集.

在f = flip const作为组合函数的示例中,我们有不同的情况,即第二个参数中的strict ⁽¹⁾,但根本不需要对其进行求值.它忽略了它的第一个.这对右折也有好处.在这里

foldr1 f [x1, x2, x3, ... ]
    ~> f x1 (foldr1 f [x2, x3, ... ])

现在最外层f可以立即评估

    ~> foldr1 f [x2, x3, ... ]
    ~> f x2 (foldr1 f [x3, ... ])
    ~> foldr1 f [x3, ... ]

并且在每个步骤中,f始终可以立即评估最外层(完全),并丢弃一个列表元素.

如果列表由生成器给出,可以在顺序消耗时在恒定空间中创建它,

last = foldr1 (flip const)

可以在恒定的空间内运行.

左边的折叠,事情是不同的.因为那是尾递归的

foldl1 f (x:y:zs) = foldl f x (y:zs) = foldl f (f x y) zs

在折叠到达列表末尾之前,它无法返回任何内容.特别是,左侧折叠永远不会终止于无限列表.

现在,看看我们的案例f = flip const,我们发现

foldl1 f [x1, x2, x3, x4, ...]
    ~> foldl f x1 [x2, x3, x4, ... ]
    ~> foldl f (f x1 x2) [x3, x4, ... ]
    ~> foldl f (f (f x1 x2) x3) [x4, ... ]

当然,这将有可能立即评估f x1 x2到x2,然后f x2 x3 = x3,但这是唯一可能为这个特殊的f.

由于foldl是一般的高阶函数,它不能在需要之前评估中间结果,因为中间结果可能永远不需要 - 事实上,这里从不需要它们,在列表的末尾,一个得到一种表达

f (f (f (f ...y3) y2) y1) y0
   ~> y0

然后f可以在不查看f构建第一个参数的大量嵌套s的情况下评估最外层.

foldl(相应的foldl1)不能知道立即评估中间结果会更有效.

严格的左侧折叠,foldl'并且foldl1'这样做,他们将中间结果评估为弱头正常形式(到最外面的值构造函数或lambda),并且

last = foldl1' (flip const)

也会非常有效率.

但是,由于中间结果的评估比使用的更多foldr,因此它们的效率会稍低,而且,重要的是,如果有任何列表元素?,则foldl1'版本将返回?:

foldl1' f [x1, ?, x3, x4]
    ~> foldl' f x1 [?, x3, x4]
    ~> case f x1 ? of
          pattern    -- that causes ?
   ~> ?

而foldr1版本没有问题,因为它根本不检查列表元素或中间结果.

⁽¹⁾即f是严格在其第二个参数是指

f x ? = ?

由于f简单地返回其第二个参数,显然就是这种情况.