从列表中提取，直到遇到副本
在Haskell中，takeWhile允许从(潜在的无限)列表中获取条目，直到某个条件不满足为止。
但是，此条件不能依赖于列表中先前的条目。
在遇到第一个重复之前，我如何从(潜在的无限)列表中获得take条目，如本例所述？
*Main> takeUntilDuplicate [1,2,3,4,5,1,2,3,4]
[1,2,3,4,5]回答 4
Stack Overflow用户
发布于 2015-02-27 01:46:51
一种方法是在遍历列表时更新一段状态，类似于在命令式语言中所做的事情。这需要与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中的测试是一元的，所以我们可以从上面使用有状态的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)示例使用(带有无限list参数)：
>>> takeUntilDuplicate (cycle [1..5])
[1,2,3,4,5]更妙的是，这些代码中有几段可以被重用来解决类似的问题。
Stack Overflow用户
发布于 2015-02-27 06:57:55
假设您正在处理Ord实例，您可以这样做。这与Luis Casillas's answer本质上是一样的，但是用折叠而不是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来显著提高性能。
Stack Overflow用户
发布于 2015-02-27 00:59:49
您认为takeWhile不起作用是因为您没有单个元素的上下文信息，这表明了以下策略:获取它。
我的This答案提到了带有上下文的装饰操作，我称之为picks (因为它向您展示了如何选择一个要关注的元素)。这是我们应该对每一件容器都免费使用的一般装潢及其上下文操作。对于列表，它是
picks :: [x] -> [(x, ([x], [x]))] -- [(x-here, ([x-before], [x-after]))]
picks [] = []
picks (x : xs) = (x, ([], xs)) : [(y, (x : ys, zs)) | (y, (ys, zs)) <- picks xs]对于无限大的列表，它是非常有效的，而我们则是这样做的。
现在和你一起去
takeUntilDuplicate :: Eq x => [x] -> [x]
takeUntilDuplicate = map fst . takeWhile (\ (x, (ys, _)) -> not (elem x ys)) . picks(奇怪的是，如果没有给予上述类型的签名，上述一行就会因为Eq的模糊性而被拒绝。)我很想问一个关于它的问题。哦，这是单形限制。(真烦人。)
备注：表示picks使用snoc列表(在右边增长的列表)交付的“元素之前”组件非常有意义(我通常也会)，更好地保持共享和从左到右的视觉效果。
https://stackoverflow.com/questions/28755554
复制相似问题
腾讯云开发者
