删除重复元素的序列

想知道如何在Seq a删除重复元素的序列

我得到一个可以做实现nub：

nubSeq :: Seq a -> Seq a 
nubSeq = fromList . nub . toList

只是想知道有没有不转换成列表，以什么标准请致电nub :: [a]->[a]？

发生在我的实现，对小块显然为主，是：

nubSeq :: (Eq a) => Seq a -> Seq a 
nubSeq = Data.Sequence.foldrWithIndex 
      (\_ x a -> case x `Data.Sequence.elemIndexR` a of 
         Just _ -> a 
         Nothing -> a |> x) Data.Sequence.empty

但一定是有什么更优雅？

谢谢。

来源

2017-08-18 esjmb

你不喜欢你的'nubSeq'对我来说似乎很好。如果你担心性能，我会建议使用['criterion']（https://hackage.haskell.org/package/criterion）进行基准测试，如果你真的想彻底 - '--dump-simpl'，输出的两个版本并进行比较。 – epsilonhalbe

不知道这是否符合更优雅，但它拆分独立功能的关注（警告：你需要a的Ord约束）：

seqToNubMap需要Seq和输出Map关联到每个a在它出现在序列
mapToList在最小索引取值和位置的Map并产生利值的ST中增加按顺序到指定的位置
nubSeq组合这些生成无重复序列

整个事情应该是O（N *的log（n）），我认为：

module NubSeq where 

import Data.Map  as Map 
import Data.List  as List 
import Data.Sequence as Seq 
import Data.Function 

seqToNubMap :: Ord a => Seq a -> Map a Int 
seqToNubMap = foldlWithIndex (\ m k v -> insertWith min v k m) Map.empty 

mapToList :: Ord a => Map a Int -> [a] 
mapToList = fmap fst . List.sortBy (compare `on` snd) . Map.toList 

nubSeq :: Ord a => Seq a -> Seq a 
nubSeq = Seq.fromList . mapToList . seqToNubMap

或者一个简单的替代方法如下@ DavidFletcher的评论：

nubSeq' :: forall a. Ord a => Seq a -> Seq a 
nubSeq' xs = Fold.foldr cons nil xs Set.empty where 

    cons :: a -> (Set a -> Seq a) -> (Set a -> Seq a) 
    cons x xs seen 
    | x `elem` seen = xs seen 
    | otherwise  = x <| xs (Set.insert x seen) 

    nil :: Set a -> Seq a 
    nil _ = Seq.empty

来源

2017-08-18 14:29:22 gallais

使用'HashMap'而不是'Map'可以提高性能。 – Shersh

如果您已经在使用不同的数据结构，为什么不使用'Seq.fromList。 Set.toList。 Set.fromList。 Seq.toList'？ – epsilonhalbe

@ epsilonhalbe - 因为它不保留排序 - 你假人 – epsilonhalbe

限制Ord的另一种方法 - 使用扫描来制作出现在列表的每个前缀中的一组元素。然后我们可以过滤掉任何已经被看到的元素。

import Data.Sequence as Seq 
import Data.Set as Set 

nubSeq :: Ord a => Seq a -> Seq a 
nubSeq xs = (fmap fst . Seq.filter (uncurry notElem)) (Seq.zip xs seens) 
    where 
    seens = Seq.scanl (flip Set.insert) Set.empty xs

或者大致相同的事，作为一个mapAccumL：

nubSeq' :: Ord a => Seq a -> Seq a 
nubSeq' = fmap fst . Seq.filter snd . snd . mapAccumL f Set.empty 
    where 
    f s x = (Set.insert x s, (x, x `notElem` s))

（如果我使用列表我会用Maybes，而不是对与布尔，那么用它代替过滤catMaybes有没有按对于序列，似乎没有catMaybes 。）

来源

2017-08-18 19:26:28

-1

我认为你的代码应该非常高效。由于序列是使用其他树型数据结构（如Map或HashMap）来存储和查找以前的项目的树型数据结构，因此对我来说没有多大意义。

相反，我拿第一个项目，并检查其余的存在。如果存在，我放弃该项目，并继续递归与其余的一样。如果不是，则构造一个新的序列，其中第一个元素是唯一元素，其余的是由其余部分提供的nubSeq的结果。应该是典型的。我使用ViewPatterns。

{-# LANGUAGE ViewPatterns #-} 
import Data.Sequence as Seq 

nubSeq :: Eq a => Seq a -> Seq a 
nubSeq (viewl -> EmptyL) = empty 
nubSeq (viewl -> (x :< xs)) | elemIndexL x xs == Nothing = x <| nubSeq xs 
          | otherwise     = nubSeq xs 

*Main> nubSeq . fromList $ [1,2,3,4,4,2,3,6,7,1,2,3,4] 
fromList [6,7,1,2,3,4]

来源

2017-08-19 12:44:33 Redu

删除重复元素的序列

回答

相关问题