Removing duplicate elements in a Seq

Question

wondering how to implement nub over a Seq a

I get that one could do:

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

Just wondering is there something standard that does not convert to Lists in order to call nub :: [a]->[a]?

An implementation that occurred to me, based obviously on nub, is:

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 

But there must be something more elegant?

thanks.

Answer 1

Not sure whether this qualifies as more elegant but it splits the concerns in independent functions (caveat: you need an Ord constraint on a):

• seqToNubMap takes a Seq and outputs a Map associating to each a the smallest index at which it appeared in the sequence

• mapToList takes a Map of values and positions and produces a list of values in increasing order according to the specified positions

• nubSeq combines these to generate a sequence without duplicates

The whole thing should be O(n*log(n)), I believe:

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

Or a simpler alternative following @DavidFletcher's comment:

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