Olist
 Contents The Olist type The construction and test for ordered lists The empty list Singular operations on ordered lists The common binary operations on sets
Description
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.
Synopsis
 type Olist a = [a] olist :: Ord a => [a] -> Olist a isOlist :: Ord a => [a] -> Bool empty :: Ord a => Olist a isEmpty :: Ord a => Olist a -> Bool member :: Ord a => a -> Olist a -> Bool insert :: Ord a => a -> Olist a -> Olist a delete :: Ord a => a -> Olist a -> Olist a included :: Ord a => Olist a -> Olist a -> Bool properlyIncluded :: Ord a => Olist a -> Olist a -> Bool disjunct :: Ord a => Olist a -> Olist a -> Bool properlyDisjunct :: Ord a => Olist a -> Olist a -> Bool equal :: Ord a => Olist a -> Olist a -> Bool union :: Ord a => Olist a -> Olist a -> Olist a intersection :: Ord a => Olist a -> Olist a -> Olist a difference :: Ord a => Olist a -> Olist a -> Olist a opposition :: Ord a => Olist a -> Olist a -> Olist a unionList :: Ord a => [Olist a] -> Olist a intersectionList :: Ord a => [Olist a] -> Olist a
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 ST 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
```