haskell - 从列表中获取直到遇到重复项

Question

在 Haskell 中，takeWhile 允许人们从(可能是无限的)列表中获取条目，直到某个条件不成立为止。

但是，此条件不能依赖于列表中的先前条目。

如何从(可能是无限的)列表中获取条目，直到遇到本例中概述的第一个重复项？

*Main> takeUntilDuplicate [1,2,3,4,5,1,2,3,4]
[1,2,3,4,5]

Answer 1

解决此问题的一种方法是在遍历列表时更新一段状态，类似于在命令式语言中所做的操作。这需要使用 State monad，如果这是您第一次，可能需要一些学习和尝试才能获得它，但相信我，这是非常值得学习的。让我们从导入开始:

import Control.Monad.State
import Data.Set (Set)
import qualified Data.Set as Set

我们要保留的状态是列表中该点之前看到的元素的Set。首先，让我们编写一对简单的 State 操作来管理可见元素集:

-- Add an element to the context Set
remember :: Ord a => a -> State (Set a) ()
remember a = modify (Set.insert a)

-- Test if the context set contains an element
haveSeen :: Ord a => a -> State (Set a) Bool
haveSeen a = do seen <- get
                return (a `Set.member` seen)

现在我们将把这两个结合到一个检查重复的操作中:

isDuplicate :: Ord a => a -> State (Set a) Bool
isDuplicate a = do seen <- haveSeen a
                   remember a
                   return seen

您提到了 takeWhile 函数。我们将沿着类似的思路构建我们的解决方案。这是 takeWhile 的定义:

-- different name to avoid collision
takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' _ [] =  []
takeWhile' p (a:as)
    | p a =  a : takeWhile p as
    | otherwise =  []

我们可以修改此函数以使用将 Bool 封装在 monad 内的谓词:

takeWhileM :: Monad m => (a -> m Bool) -> [a] -> m [a]
takeWhileM _ [] = return []
takeWhileM p (a:as) = 
    do test <- p a
       if test
       then do rest <- takeWhileM p as
               return (a:rest)
       else return []

但这里的关键区别在于，由于 takeWhileM 中的测试是单子(monad)的，因此我们可以使用上面的有状态 isDuplicate 。因此，每次我们使用 isDuplicate 测试列表中的元素时，我们也会将该元素记录在正在通过计算进行线程化的 Set 中。所以现在我们可以像这样编写takeUntilDuplicate:

takeUntilDuplicate :: Ord a => [a] -> [a]
takeUntilDuplicate as = evalState (takeUntilDuplicate' as) Set.empty
    where takeUntilDuplicate' :: Ord a => [a] -> State (Set a) [a]
          takeUntilDuplicate' = takeWhileM (fmap not . isDuplicate)

使用示例(带有无限列表参数):

 >>> takeUntilDuplicate (cycle [1..5])
 [1,2,3,4,5]

巧妙的是，其中几段代码可以重复用于类似的问题。