Haskell中构建String应选用foldr还是foldl'？

问题描述 #

我之前的思路是：构建数据结构用foldr，结果是单一值用foldl'，但处理String时拿不准选哪个。一方面String属于数据结构，另一方面它常被整体使用，短路特性作用不大。想知道putStrLn这类函数对String的使用方式是不是关键判断依据？或者我的思路完全错了？

编辑：我要实现一个函数，把[(5, 's'), (1, 'a'), (3, 'd')]这样的输入转换成sssssaddd，现在有两个实现可选：

decode :: [(Int, Char)] -> String
decode = foldr ff []
  where
    ff (l, c) xs = replicate l c ++ xs

decode' :: [(Int, Char)] -> String
decode' = foldl' ff []
  where
    ff xs (l, c) = xs ++ replicate l c

解答 #

核心结论：选decode（foldr实现）更高效 #

• Haskell里的String本质是[Char]，也就是字符链表。链表的++操作有个关键特性：左边链表越长，拼接耗时越长，因为它必须遍历整个左链表才能找到末尾来连接右链表。
• 看foldl'版本的decode'：每次迭代执行xs ++ replicate l c，其中xs是之前累积的结果。随着迭代推进，xs会越来越长，每次++都要完整遍历一次xs，整体时间复杂度是O(n²)，数据量大时效率会急剧下降。
• 再看foldr版本的decode：每次执行replicate l c ++ xs，这里replicate l c是长度固定的短链表，xs是后续递归生成的链表。这种情况下++只需要遍历左边的短链表，直接把它的末尾指向右边的链表即可，整体时间复杂度是O(n)，效率远高于前者。

对初始思路的修正 #

你的初始思路有一定合理性，但针对String这种链表结构，关键判断依据不是“是否整体使用”或者putStrLn的调用方式，而是链表的拼接效率特性。putStrLn处理String时只是遍历输出，不管哪种方式生成的结果，输出效率都一样，但生成结果的过程效率差异巨大。

另外，foldr的短路特性在这里确实用不上，但它的链表拼接效率优势是决定性的。

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