代码之家 › 专栏 › 技术社区 › Joseph Sible-Reinstate Monica

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

infinite-sequence fold haskell

Joseph Sible-Reinstate Monica · 技术社区 · 6 年前

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

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 总是需要评估它的第二个参数。这是不是可以用更聪明的 单一助手 或者说,使用折叠来完成这项任务本质上是不可能的?

3 回复 | 直到 6 年前

willeM_ Van Onsem 6 年前

您可以将元素的移除转移到尾部,因此无论值如何,我们首先产量 “ 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 ,然后稍后再担心下一个元素。如果第二个参数(列表尾部的折叠列表)包含相同的元素,那么我们将“删除”它,否则,我们将保留整个列表。

上面还可以生成 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 其次是A 1 ,那 1个 从不发射:

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

Ed'ka 6 年前

您只需结合您的实现:

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]

Will Ness Derri Leahy 6 年前

您的第一个代码段产生了许多代码段中的第一个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) .

我总是用 r 作为减速器第二个参数的名称,作为 R 危急的 R “…”在这之后又出现了另一个争论 R 在里面 g 的定义意味着 R 是一个函数,我们可以传递一个作为状态的更新值。

此技术允许使用 foldr 对有状态的计算进行编码,例如 take , drop , 滴滴 , 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]