通过折叠从无限列表中删除连续的重复项？

Question

考虑从列表中删除连续重复项的函数的这些实现之一：

uniq :: Eq a => [a] -> [a]
uniq [] = []
uniq (x:xs) = x:uniq (dropWhile (x ==) xs)

uniq :: Eq a => [a] -> [a]
uniq (x:xs@(y:_))
 | x == y    = x:tail (uniq xs)
 | otherwise = x:uniq xs
uniq l = l

它们在有限列表和无限列表上都按预期工作。更具体地说，对于无限列表，只要在 return.[=18= 的 n 值之前没有无限长的重复值序列，我希望 take n $ uniq l 终止]

现在考虑使用 foldr:

对这种功能的尝试

uniq :: (Foldable t, Eq a) => t a -> [a]
uniq = foldr uniqHelper []
 where uniqHelper x [] = [x]
       uniqHelper x acc@(y:_)
        | x == y    =   acc
        | otherwise = x:acc

这适用于有限列表，但永远不会终止无限列表，因为 uniqHelper 总是需要计算它的第二个参数。这是可以用更聪明的方法解决的问题吗uniqHelper，或者说使用折叠来完成这个任务本质上是不可能的？

Answer 1

可以把一个元素的移除转移到尾部，所以不管值如何，我们先“yield”x，然后我们用一个函数（此处tl）评估列表的尾部：

uniq :: (Foldable t, Eq a) => t a -> [a]
uniq = foldr uniqHelper []
 where uniqHelper x acc = x : tl acc
           where tl acc@(x2:xs) | x == x2 = xs
                                | otherwise = acc
                 tl [] = []

因此我们首先让出x，然后再考虑下一个元素。如果第二个参数（列表尾部的折叠列表）包含相同的元素，那么我们"remove"它，否则，我们保留整个列表。

上面也可以得到一个repeat的第一个元素，例如：

Prelude> head (uniq (repeat 1))
1
Prelude> take 5 $ uniq [1..]
[1,2,3,4,5]
Prelude> uniq [1,1,1,1,2,2,2,1,1,1,1,1,1,3,3,3,3,1,1]
[1,2,1,3,1]

当然，如果有无限数量的 0 后跟 1，则永远不会发出 1：

Prelude> uniq (repeat 0 ++ [1])
[0

Answer 2

您的第一个代码片段生成了许多代码片段中的第一个 x，但第三个代码片段生成最后一个 x，这就是出现差异的原因。

为了忠实地将第一个片段呈现为正确的折叠，我们折叠成函数，以便我们可以传递状态参数，偶尔更新为列表的新的唯一元素：

uniq [] = []
uniq (x:xs) = x : foldr g (const []) xs x
  where
  g y r x | y==x  =     r x
      | otherwise = y : r y

这实际上跳过了重复项，而不是像其他两个答案那样一遍又一遍地重新考虑然后忽略它们，这实际上是彼此等效的：dropWhile could only skip over no不止一个元素，随后调用 its dropWhile (==x) 的 reducer 将跳过这些元素。

我一直用r作为reducer的第二个参数的名字，作为“r递归r[=39=的助记符]结果”。这里在 g 的定义中 r 之后存在另一个参数意味着 r 是一个函数，我们可以将更新后的值作为状态传递给它。

此技术允许使用 foldr 对状态计算进行编码，例如 take、drop、dropWhile、takeWhile、etc.。

> head $ uniq $ repeat 1 1 > take 10 $ uniq [n | n <- [1..], n <- replicate n n] [1,2,3,4,5,6,7,8,9,10] > uniq [1..10] [1,2,3,4,5,6,7,8,9,10]

Answer 3

您可以组合您的实现：

uniq :: Eq a => [a] -> [a]
uniq = foldr uniqHelper []
  where uniqHelper x acc = x : dropWhile (==x) acc

在无限列表上获得所需的行为：

Prelude> take 5 $ uniq [1..]
[1,2,3,4,5]

通过折叠从无限列表中删除连续的重复项？

Remove consecutive duplicates from an infinite list via folding?

haskell

fold

infinite-sequence