刪除重複元素的序列

想知道如何在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

刪除重複元素的序列

回答

相關問題