alternate-datatype-representations.lhs

> {-# LANGUAGE GADTs #-}
>
> import Prelude hiding (filter, null)
> import qualified Data.List as L
> import qualified Data.Set as S
>
> data FlexiSet a where
>   EqSet  :: Eq a => [a] -> FlexiSet a
>   OrdSet :: Ord a => S.Set a -> FlexiSet a
>
> makeEqSet :: Eq a => [a] -> FlexiSet a
> makeEqSet = EqSet . L.nub
>
> makeOrdSet :: Ord a => [a] -> FlexiSet a
> makeOrdSet = OrdSet . S.fromList
>
> toList :: FlexiSet a -> [a]
> toList (EqSet  as) = as
> toList (OrdSet as) = S.toList as
>
> mapEq :: Eq b => (a -> b) -> FlexiSet a -> FlexiSet b
> mapEq f = EqSet . L.nub . map f . toList
>
> mapOrd :: Ord b => (a -> b) -> FlexiSet a -> FlexiSet b
> mapOrd f = OrdSet . S.fromList . map f . toList
>
> filter :: (a -> Bool) -> FlexiSet a -> FlexiSet a
> filter f (EqSet  as) = EqSet (L.filter f as)
> filter f (OrdSet as) = OrdSet (S.filter f as)
>
> insert :: a -> FlexiSet a -> FlexiSet a
> insert a (EqSet  as) = EqSet (L.nub (a:as))
> insert a (OrdSet as) = OrdSet (S.insert a as)
>
> delete :: a -> FlexiSet a -> FlexiSet a
> delete a (EqSet  as) = EqSet (L.filter (/=a) as)
> delete a (OrdSet as) = OrdSet (S.delete a as)
>
> member :: a -> FlexiSet a -> Bool
> member a (EqSet  as) = any (==a) as
> member a (OrdSet as) = S.member a as
>
> null :: FlexiSet a -> Bool
> null (EqSet  as) = L.null as
> null (OrdSet as) = S.null as
>
> size :: FlexiSet a -> Int
> size (EqSet  as) = length as
> size (OrdSet as) = S.size as
>
> union :: FlexiSet a -> FlexiSet a -> FlexiSet a
> union (EqSet  as) (EqSet  bs) = EqSet (L.nub (as ++ bs))
> union (EqSet  as) (OrdSet bs) = OrdSet (S.union (S.fromList as) bs)
> union (OrdSet as) (EqSet  bs) = OrdSet (S.union as (S.fromList bs))
> union (OrdSet as) (OrdSet bs) = OrdSet (S.union as bs)
>
> intersection :: FlexiSet a -> FlexiSet a -> FlexiSet a
> intersection (EqSet  as) (EqSet  bs) = EqSet (L.filter (`elem` bs) as)
> intersection (EqSet  as) (OrdSet bs) = OrdSet (S.intersection (S.fromList as) bs)
> intersection (OrdSet as) (EqSet  bs) = OrdSet (S.intersection as (S.fromList bs))
> intersection (OrdSet as) (OrdSet bs) = OrdSet (S.intersection as bs)
>
> difference :: FlexiSet a -> FlexiSet a -> FlexiSet a
> difference (EqSet  as) (EqSet  bs) = EqSet (L.filter (`notElem` bs) as)
> difference (EqSet  as) (OrdSet bs) = OrdSet (S.difference (S.fromList as) bs)
> difference (OrdSet as) (EqSet  bs) = OrdSet (S.difference as (S.fromList bs))
> difference (OrdSet as) (OrdSet bs) = OrdSet (S.difference as bs)
>
> disjointUnion :: FlexiSet a -> FlexiSet b -> FlexiSet (Either a b)
> disjointUnion (EqSet  as) (EqSet  bs) = EqSet (map Left as ++ map Right bs)
> disjointUnion (EqSet  as) (OrdSet bs) = EqSet (map Left as ++ map Right (S.toList bs))
> disjointUnion (OrdSet as) (EqSet  bs) = EqSet (map Left (S.toList as) ++ map Right bs)
> disjointUnion (OrdSet as) (OrdSet bs) = OrdSet (S.disjointUnion as bs)