{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveGeneric #-}
module Dhall.Set (
Set(..)
, toList
, toSet
, toSeq
, fromList
, append
, empty
, difference
) where
import Prelude
import Data.List (foldl')
import Data.Sequence (Seq, (|>))
import Data.Data (Data)
import GHC.Generics (Generic)
import qualified Data.Set
import qualified Data.Sequence
import qualified Data.Foldable
data Set a = Set (Data.Set.Set a) (Seq a)
deriving (Eq, Generic, Ord, Show, Data)
instance Foldable Set where
foldMap f = foldMap f . toSeq
toSet :: Set a -> Data.Set.Set a
toSet (Set s _) = s
toSeq :: Set a -> Seq a
toSeq (Set _ xs) = xs
toList :: Set a -> [a]
toList = Data.Foldable.toList
fromList :: Ord a => [a] -> Set a
fromList = foldl' (flip append) empty
append :: Ord a => a -> Set a -> Set a
append x os@(Set s xs)
| Data.Set.member x s = os
| otherwise = Set (Data.Set.insert x s) (xs |> x)
empty :: Set a
empty = Set Data.Set.empty Data.Sequence.empty
difference :: Ord a => Set a -> Set a -> [a]
difference os (Set s _) =
filter (\ x -> not (Data.Set.member x s)) (toList os)