4

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

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

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

现在考虑这种功能的尝试，使用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问题，还是本来就不可能使用折叠来完成这项任务？

4

3 回答 3

3

您可以将元素的移除转移到尾部，因此无论值如何，我们首先“ 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 [] = []

因此，我们首先 yield x，然后再担心下一个元素。如果第二个参数（列表尾部的折叠列表）包含相同的元素，那么我们“删除”它，否则，我们保留整个列表。

以上也能够产生 a 的第一个元素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]

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

Prelude> uniq (repeat 0 ++ [1])
[0
于 2018-12-08T17:35:26.660 回答
1

您可以组合您的实现：

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]
于 2018-12-09T02:13:31.213 回答
1

您的第一个片段产生了许多中的第一个 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只能跳过不超过一个元素，然后将被跳过通过以下减速器调用其 dropWhile (==x).

我总是使用rreducer 第二个参数的名称，作为“ r ecursive r esult”的助记符。r在in的定义之后存在另一个参数g意味着它r是一个函数，我们可以传递一个更新的值作为状态。

这种技术可以foldr用来编码有状态的计算，如take, drop, dropWhile,等。takeWhile

> 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]
于 2018-12-08T19:51:33.697 回答