拼接带指定分隔符的字符串列表，foldl与foldr哪个效率更高？

foldl不仅不比foldr高效，反而效率低很多，原因和Haskell字符串的特性、++操作的实现以及两种fold的执行逻辑直接相关：

1. Haskell字符串与++的特性
   Haskell里的字符串是[Char]，本质是单链表结构。++操作的实现逻辑是：遍历左边列表的所有元素，把右边列表接在左边的末尾，时间复杂度为O(length 左边列表)——左边越长，拼接耗时越久。

2. foldr的执行逻辑与效率
   你的foldr实现是：

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

由于++是右结合运算符，实际等价于a ++ ("-----\n" ++ b)。foldr从列表末尾往前处理元素，最终的拼接顺序是：

s1 ++ ("-----\n" ++ (s2 ++ ("-----\n" ++ (... ++ sn)...)))

每一步只需要遍历当前字符串s_i和分隔符，将它们接在已经构造好的后续结果前。所有字符串和分隔符都只会被遍历一次，总时间复杂度是线性的（与所有字符串的总长度成正比）。

3. foldl的执行逻辑与效率
   如果用foldl实现（需要先处理边界避免首元素前加分隔符），写法大致是：

foldl (\acc x -> acc ++ "-----\n" ++ x) (head xs) (tail xs)

foldl从列表开头往右处理元素，拼接顺序是左结合的：

(((s1 ++ "-----\n") ++ s2) ++ "-----\n") ++ s3 ...

每一步的acc是前面所有元素拼好的长字符串，acc ++ "-----\n"需要遍历整个acc，后续和s_i拼接又要遍历这个新的长字符串（acc+分隔符）。比如第一个字符串s1会在每一次后续拼接中被重复遍历，遍历次数等于它后面的元素个数。当列表较长时，总时间复杂度会变成平方级别，效率急剧下降。

综上，这个场景下foldr的效率远高于foldl，因为它利用链表特性避免了重复遍历前面的字符串。

内容的提问来源于stack exchange，提问作者vkryuu