{- | An 'Olist' is an /ordered list/. The main function of this module is the implementation of the finite subset structure of a given type @a@. Finite sets are represented as ordered lists and the basic set functions and relations like 'union', 'intersection', 'included' etc. are provided. -} module Olist ( -- * The @Olist@ type Olist, -- * The construction and test for ordered lists olist, -- | For example, -- -- > > olist ["b", "c", "b", "a", "c", "a"] -- > ["a","b","c"] -- -- As the example shows, multiple occuring members are deleted. -- -- (The implementation builts the ordered list with component-wise 'insert' and that is not an optimal sorting algorithm in general. -- But it is optimal, when the argument is an already ordered list. We use 'olist' only as a an additional safety-mechanism for -- functions like @ext :: p -> [a] -> p@, where in most cases the second argument will usually be an @Olist a@ value, anyway.) isOlist, -- | Checks if the given argument is ordered. -- * The empty list empty, -- | Returns the empty list @[]@, i.e. -- -- > > Olist.empty -- > [] -- -- (Note, that there is also an @empty@ function in the @Costack@ module.) isEmpty, -- | Checks on emptiness; i.e. it is the same as the Haskell native @null@. -- -- > > isEmpty [1,2,3] -- > False -- * Singular operations on ordered lists member, -- | For example, -- -- > > member 7 [3,5,7,9] -- > True -- > > 4 `member` [2,3,4,5] -- > True insert, -- | For example, -- -- > > insert 7 [3,5,9,11] -- > [3,5,7,9,11] -- > > insert 7 [3,5,7,9,11] -- > [3,5,7,9,11] delete, -- | For example, -- -- > > delete 7 [3,5,7,9,11] -- > [3,5,9,11] -- > > delete 7 [3,5,9,11] -- > [3,5,9,11] -- * The common binary operations on sets -- | These functions all assume, that the arguments are actually 'Olist' values. Otherwise, the function doesn't terminate with an -- error, it just produces unintended results. included, -- | Implementation of ⊆ on (finite) sets. For example, -- -- > > included "acd" "abcd" -- recall, that "acd" is the list ['a', 'c', 'd'] -- > True -- > > [2,4] `included` [1,2,3,4,5] -- > True properlyIncluded, -- | Implementation of the strict version ⊂ of ⊆, i.e. the first argument must be included, but different to the second one. disjunct, -- | Two finite sets, i.e. two ordered lists are /disjunct/ iff they do not have a common member. For example -- -- > > disjunct "acd" "bef" -- > True -- > > "abc" `disjunct` "bef" -- > False -- > > [] `disjunct` [1,2,3] -- > True properlyDisjunct, -- | Two finite sets are /properly disjunct/ iff they are disjunct and none of them is empty. -- -- > > [] `properlyDisjunct` [1,2,3] -- > False equal, -- | The equality of two finite sets; actually it is just another name for @(==)@ on ordered lists. union, -- | The implementation of ∪, for example -- -- > > [1,2,4,5] `union` [1,3,5,7] -- > [1,2,3,4,5,7] intersection, -- | The implementation of ∩, for example -- -- > > [1,2,4,5] `intersection` [1,3,5,7] -- > [1,5] difference, -- | Implementation of the difference operator \ on sets. For example, -- -- > > [1,2,4,5] `difference` [1,3,5,7] -- > [2,4] opposition, -- | The /opposition/ or /symmetric difference/ @S@∇@T@ of two sets @S@, @T@ is defined as @(S\T)∪(T\S)@. For example, -- -- > > [1,2,4,5] `opposition` [1,3,5,7] -- > [2,3,4,7] unionList, -- | Returns the union of a list of ordered lists. For example, -- -- > > unionList [[1,3,5], [1,2,3], [1,5,9]] -- > [1,2,3,5,9] -- > > unionList [] -- > [] intersectionList, -- | Returns the intersection of a list of ordered lists. The result is undefined for the empty list. -- -- > > intersectionList [[1,3,5], [1,2,3], [1,5,9]] -- > [1] -- > > intersectionList [] -- > *** Exception: Olist.intersectionList: not defined for empty list argument ) where --------------------------------------------------------------------------------------------------------------- -- the type of ordered lists type Olist a = [a] -- order list construction olist :: Ord a => [a] -> Olist a olist [] = [] olist (a:aL) = insert a (olist aL) isOlist :: Ord a => [a] -> Bool isOlist [] = True isOlist [a] = True isOlist (a:b:cL) = (a < b) && isOlist (b:cL) -- empty list empty :: Ord a => Olist a empty = [] isEmpty :: Ord a => Olist a -> Bool isEmpty = null -- singular operations member :: Ord a => a -> Olist a -> Bool member a [] = False member a (b:bL) = case compare a b of LT -> False EQ -> True GT -> member a bL insert :: Ord a => a -> Olist a -> Olist a insert a [] = [a] insert a (b:bL) = case compare a b of LT -> a:b:bL EQ -> b:bL GT -> b : (insert a bL) delete :: Ord a => a -> Olist a -> Olist a delete a [] = [] delete a (b:bL) = case compare a b of LT -> b:bL EQ -> bL GT -> b : (delete a bL) -- binary operations included :: Ord a => Olist a -> Olist a -> Bool included [] bL = True included aL [] = False included (a:aL) (b:bL) = case compare a b of LT -> False EQ -> included aL bL GT -> included (a:aL) bL properlyIncluded :: Ord a => Olist a -> Olist a -> Bool properlyIncluded [] [] = False properlyIncluded [] bL = True properlyIncluded aL [] = False properlyIncluded (a:aL) (b:bL) = case compare a b of LT -> False EQ -> properlyIncluded aL bL GT -> included (a:aL) bL disjunct :: Ord a => Olist a -> Olist a -> Bool disjunct [] bL = True disjunct bL [] = True disjunct (a:aL) (b:bL) = case compare a b of LT -> disjunct aL (b:bL) EQ -> False GT -> disjunct (a:aL) bL properlyDisjunct :: Ord a => Olist a -> Olist a -> Bool properlyDisjunct [] bL = False properlyDisjunct bL [] = False properlyDisjunct (a:aL) (b:bL) = case compare a b of LT -> disjunct aL (b:bL) EQ -> False GT -> disjunct (a:aL) bL equal :: Ord a => Olist a -> Olist a -> Bool equal = (==) union :: Ord a => Olist a -> Olist a -> Olist a union [] bL = bL union aL [] = aL union (a:aL) (b:bL) = case compare a b of LT -> a : (union aL (b:bL)) EQ -> a : (union aL bL) GT -> b : (union (a:aL) bL) intersection :: Ord a => Olist a -> Olist a -> Olist a intersection [] bL = [] intersection aL [] = [] intersection (a:aL) (b:bL) = case compare a b of LT -> intersection aL (b:bL) EQ -> a : (intersection aL bL) GT -> intersection (a:aL) bL difference :: Ord a => Olist a -> Olist a -> Olist a difference [] bL = [] difference aL [] = aL difference (a:aL) (b:bL) = case compare a b of LT -> a : (difference aL (b:bL)) EQ -> difference aL bL GT -> difference (a:aL) bL opposition :: Ord a => Olist a -> Olist a -> Olist a opposition [] bL = bL opposition aL [] = aL opposition (a:aL) (b:bL) = case compare a b of LT -> a : (opposition aL (b:bL)) EQ -> opposition aL bL GT -> b : (opposition (a:aL) bL) unionList :: Ord a => [Olist a] -> Olist a unionList = foldl union [] intersectionList :: Ord a => [Olist a] -> Olist a intersectionList [] = error "Olist.intersectionList: not defined for empty list argument" intersectionList aL = foldl1 intersection aL