foldl 或foldr 对于插入列表元素更有效吗？

Question

| l > 1     = foldr (\a b -> a ++ "-----\n" ++ b) "" xs

xs

是一个字符串列表，其目的是用五个破折号和一个换行符连接列表中的每个元素。

在这种情况下使用

foldl

或

foldr

会更有效吗？为什么？我知道

intercalate

很适合这个目的，但就我而言，我不能使用导入。

Answer 1

foldr

在这里更好，因为

++

（以及一般的列表）是“自然”右关联的。

++

的定义是：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

请注意，第二个参数

ys

在两个方程中均未修改，而第一个列表被分开，并将其元素添加到正在构造的新列表的前面。因此，出现在 ++ 的

left

上的东西必须被扫描和重建，而出现在右边的东西则无需花费任何费用。即使我们完全展开

++

的递归定义，如下所示：

let xs = [x1, x2, x3, x4]
 in xs ++ ys

然后我们得到

x1 : x2 : x3 : x4 : ys

；

ys

只是按原样存储在数据构造函数的字段中（最深嵌套的

:

），因此永远不会被

++

的工作检查。但是整个

xs

列表必须被遍历并重建到

ys

的前面。

因此，当我们折叠构建一个列表时，我们要确保累积参数（随着我们处理更多列表，它会变得越来越大）始终用作 ++ 的 right

 参数

。这样就不需要在折叠的每一层重新遍历。

所以

foldr (\a b -> a ++ "-----\n" ++ b) "" xs

很好；它是

b

参数，它接收折叠列表其余部分的结果，并且它被用作

++

的正确参数，根本不需要检查它。这意味着每层折叠的成本是遍历

a

的成本和遍历

"-----\n"

的成本。整个折叠的成本只是所有

a

值的成本总和（因此

xs

中列表的长度之和），加上一些等于数字的小固定字符串

xs

中的元素。

如果我们使用像

foldl (\b a -> b ++ "-----\n" ++ a) "" xs

这样的左折叠，情况会更糟。这里折叠的每一层都使用

a

右侧的列表 (

++

) 的元素，并使用左侧的先前结果

b

。因此，我们保持

a

不变，并且必须遍历

b

以将其所有元素添加到

a

的前面。这在折叠底部很好，其中

b

是

""

起始值。但在水平上，

b

将是折叠第一个a字符串（加上

"-----\n"

分隔符字符串）的

结果

，所以无论如何我们都必须遍历该

a

字符串。然后再次平移

b

将是

++

将另一个字符串放到其前面的结果，因此我们必须遍历该新字符串 plus 再次遍历第一个字符串。以这种方式折叠 N 个元素的整个列表时，我们最终会遍历第一个字符串 N 次，第二个字符串 N-1 次，依此类推。这比使用右折叠要昂贵得多。