从列表中取出直到遇到重复

Question

在Haskell中,takeWhile允许从一个(可能是无限的)列表中获取条目,直到某个条件不成立.

但是,此条件不能取决于列表的先前条目.

take在我遇到本例中概述的第一个副本之前,如何从(可能是无限的)列表中输入条目？

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

Answer 1

解决这个问题的一种方法是在遍历列表时更新一个状态,类似于您在命令式语言中所做的操作.这需要与Statemonad合作,如果这是你的第一次,可能需要一些学习和玩耍来获得它,但相信我,这是值得学习的.让我们从导入开始:

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是monadic,我们可以使用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]

什么是巧妙的是,这些代码中的一些可以重用于类似的问题.

Answer 2

假设您正在处理Ord实例,您可以这样做.这与路易斯·卡西利亚斯的回答基本相同,但是使用折叠代替State.我们的每个答案都使用了不同的普遍适用的技术.路易斯包括对他的一个很好的解释; 我的经典解释是格雷厄姆赫顿的"折叠的普遍性和表现力的教程".

import Data.Set (member)
import qualified Data.Set as S

takeUntilDuplicate :: Ord a => [a] -> [a]
takeUntilDuplicate xs = foldr go (const []) xs S.empty
  where
    go x cont set
      | x `member` set = []
      | otherwise      = x : cont (S.insert x set)

如果您实际上正在处理Int(或任何可以Int快速转换为的东西),您可以通过使用Data.IntSet或Data.HashSet代替来大幅提高性能Data.Set.