function - 使用折叠插入

Question

有人可以解释一下如何使用 Fold 编写 intercalate 函数吗？此外，我听说过 foldr 或 foldl；其中哪一个最适合在这种情况下使用？

这是我的递归尝试:

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

Answer 1

使用foldr1:

intercalate' :: [a] -> [[a]] -> [a]
intercalate' _ [] = []
intercalate' x xs = foldr1 (\a acc -> a ++ x ++ acc) xs

这将在每个元素之间使用 x 插入右侧的值。 (尽管它这样做 lazily 。–直到需要时才会评估整个折叠。)

foldr1 和 foldr 的相似之处在于它们都是从右侧折叠。区别在于前者不要求我们提供最终期限，而后者则需要提供最终期限。这需要我们对空列表进行模式匹配，否则会抛出异常。

事实上，foldl1也可以实现插层。但是，强烈建议不要这样做，因为左侧折叠会急切地消耗输入。

intercalate' :: [a] -> [[a]] -> [a]
intercalate' _ [] = []
intercalate' x xs = foldl1 (\acc a -> acc ++ x ++ a) xs

<小时/>

为了进一步强调对右折叠的偏好，请考虑以下组合:

take 10 . intercalate' [0] $ repeat [1..3]

看起来无害。但是使用 foldl1 将急切地消耗无限列表，而不是停止该过程。

但是，使用 foldr1 将延迟计算并给出 [1,2,3,0,1,2,3,0,1,2]。 (intercalate' 将临时计算 [1..3]++ [0]++ (foldr (...) [0] [elem1 ... elemN]) 在 take 10 之前询问主要术语并评估折叠。)

感谢Will .

有用的阅读:
foldl versus foldr behaviour with infinite lists