-- | simple Implementierung,
-- die möglichst lazy ist

module Autolib.Simple_Set

( Set, -- abstrakt exportiert
        emptySet,     -- :: Set a
	mkSet,        -- :: Ord a => [a]  -> Set a
	setToList,    -- :: Set a -> [a] 
	unitSet,      -- :: a -> Set a
	singletonSet, -- :: a -> Set a

	union,          -- :: Ord a => Set a -> Set a -> Set a
	unionManySets,  -- :: Ord a => [Set a] -> Set a
	minusSet,       -- :: Ord a => Set a -> Set a -> Set a
	mapSet,         -- :: Ord a => (b -> a) -> Set b -> Set a
	intersect,      -- :: Ord a => Set a -> Set a -> Set a

	elementOf,      -- :: Ord a => a -> Set a -> Bool
	isEmptySet,     -- :: Set a -> Bool
	
	cardinality     -- :: Set a -> Int
)

where

import Data.List ( nub, (\\) )

data Set a = Set { forall a. Set a -> [a]
contents :: [ a ] }
     deriving (Set a -> Set a -> Bool
(Set a -> Set a -> Bool) -> (Set a -> Set a -> Bool) -> Eq (Set a)
forall a. Eq a => Set a -> Set a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Set a -> Set a -> Bool
== :: Set a -> Set a -> Bool
$c/= :: forall a. Eq a => Set a -> Set a -> Bool
/= :: Set a -> Set a -> Bool
Eq)


emptySet :: Set a
emptySet :: forall a. Set a
emptySet = [a] -> Set a
forall a. [a] -> Set a
Set []

mkSet :: Ord a => [a]  -> Set a
mkSet :: forall a. Ord a => [a] -> Set a
mkSet = [a] -> Set a
forall a. [a] -> Set a
Set ([a] -> Set a) -> ([a] -> [a]) -> [a] -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Eq a => [a] -> [a]
nub

setToList :: Set a -> [a] 
setToList :: forall a. Set a -> [a]
setToList = Set a -> [a]
forall a. Set a -> [a]
contents

unitSet :: a -> Set a
unitSet :: forall a. a -> Set a
unitSet a
x = [a] -> Set a
forall a. [a] -> Set a
Set [ a
x ]

singletonSet :: a -> Set a
singletonSet :: forall a. a -> Set a
singletonSet = a -> Set a
forall a. a -> Set a
unitSet

union :: Ord a => Set a -> Set a -> Set a
union :: forall a. Ord a => Set a -> Set a -> Set a
union Set a
xs Set a
ys = [a] -> Set a
forall a. Ord a => [a] -> Set a
mkSet ( Set a -> [a]
forall a. Set a -> [a]
contents Set a
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ Set a -> [a]
forall a. Set a -> [a]
contents Set a
ys )

unionManySets :: Ord a => [Set a] -> Set a
unionManySets :: forall a. Ord a => [Set a] -> Set a
unionManySets = [a] -> Set a
forall a. Ord a => [a] -> Set a
mkSet ([a] -> Set a) -> ([Set a] -> [a]) -> [Set a] -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[a]] -> [a]) -> ([Set a] -> [[a]]) -> [Set a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Set a -> [a]) -> [Set a] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map Set a -> [a]
forall a. Set a -> [a]
contents

minusSet :: Ord a => Set a -> Set a -> Set a
minusSet :: forall a. Ord a => Set a -> Set a -> Set a
minusSet Set a
xs Set a
ys = [a] -> Set a
forall a. Ord a => [a] -> Set a
mkSet ( Set a -> [a]
forall a. Set a -> [a]
contents Set a
xs [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
\\ Set a -> [a]
forall a. Set a -> [a]
contents Set a
ys )

mapSet :: Ord a => (b -> a) -> Set b -> Set a
mapSet :: forall a b. Ord a => (b -> a) -> Set b -> Set a
mapSet b -> a
f = [a] -> Set a
forall a. Ord a => [a] -> Set a
mkSet ([a] -> Set a) -> (Set b -> [a]) -> Set b -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> a) -> [b] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map b -> a
f ([b] -> [a]) -> (Set b -> [b]) -> Set b -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set b -> [b]
forall a. Set a -> [a]
contents

intersect :: Ord a => Set a -> Set a -> Set a
intersect :: forall a. Ord a => Set a -> Set a -> Set a
intersect Set a
xs Set a
ys = [a] -> Set a
forall a. Ord a => [a] -> Set a
mkSet ( (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` Set a -> [a]
forall a. Set a -> [a]
contents Set a
ys) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ Set a -> [a]
forall a. Set a -> [a]
contents Set a
xs )

elementOf :: Ord a => a -> Set a -> Bool
elementOf :: forall a. Ord a => a -> Set a -> Bool
elementOf a
x Set a
xs = a
x a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` Set a -> [a]
forall a. Set a -> [a]
contents Set a
xs

isEmptySet :: Set a -> Bool
isEmptySet :: forall a. Set a -> Bool
isEmptySet = [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([a] -> Bool) -> (Set a -> [a]) -> Set a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> [a]
forall a. Set a -> [a]
contents
	
cardinality :: Set a -> Int
cardinality :: forall a. Set a -> Int
cardinality = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> (Set a -> [a]) -> Set a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> [a]
forall a. Set a -> [a]
contents