Olist

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.

The Olist type

type Olist a = [a]

The construction and test for ordered lists

olist :: Ord a => [a] -> Olist a

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 :: Ord a => [a] -> Bool

Checks if the given argument is ordered.

The empty list

empty :: Ord a => Olist a

Returns the empty list [], i.e.

 > Olist.empty
 []

(Note, that there is also an empty function in the Costack module.)

isEmpty :: Ord a => Olist a -> Bool

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 :: Ord a => a -> Olist a -> Bool

For example,

 > member 7 [3,5,7,9]
 True
 > 4 `member` [2,3,4,5]
 True

insert :: Ord a => a -> Olist a -> Olist a

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 :: Ord a => a -> Olist a -> Olist a

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 :: Ord a => Olist a -> Olist a -> Bool

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 :: Ord a => Olist a -> Olist a -> Bool

Implementation of the strict version ⊂ of ⊆, i.e. the first argument must be included, but different to the second one.

disjunct :: Ord a => Olist a -> Olist a -> Bool

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 :: Ord a => Olist a -> Olist a -> Bool

Two finite sets are properly disjunct iff they are disjunct and none of them is empty.

 > [] `properlyDisjunct` [1,2,3]
 False

equal :: Ord a => Olist a -> Olist a -> Bool

The equality of two finite sets; actually it is just another name for (==) on ordered lists.

union :: Ord a => Olist a -> Olist a -> Olist a

The implementation of ∪, for example

 > [1,2,4,5] `union` [1,3,5,7]
 [1,2,3,4,5,7]

intersection :: Ord a => Olist a -> Olist a -> Olist a

The implementation of ∩, for example

 > [1,2,4,5] `intersection` [1,3,5,7]
 [1,5]

difference :: Ord a => Olist a -> Olist a -> Olist a

Implementation of the difference operator \ on sets. For example,

 > [1,2,4,5] `difference` [1,3,5,7]
 [2,4]

opposition :: Ord a => Olist a -> Olist a -> Olist a

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 :: Ord a => [Olist a] -> Olist a

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 :: Ord a => [Olist a] -> Olist a

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