时间戳

首页 > 解决方案 > 使用折叠插入

function - 使用折叠插入

问题描述

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

这是我的递归尝试：

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

标签： functionhaskellfold

解决方案

使用foldr1：

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

这将在每个元素之间插入右侧的值。x（尽管它懒惰地这样做。-直到需要时才评估整个折叠。）

两者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会急切地消耗无限列表，而不是停止进程。

但是， usingfoldr1将延迟评估并给出正确的结果[1,2,3,0,1,2,3,0,1,2]。（在询问前导词和评估折叠之前intercalate'会临时评估。）[1..3] ++ [0] ++ (foldr (...) [0] [elem1 ... elemN])take 10

向威尔致敬。

有用的阅读：
foldl与foldr无限列表的行为对比

推荐阅读