PropLogic-0.9.0.1: A system for propositional logic with default and fast instances of propositional algebras.

Olist

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

# The `Olist` type

type Olist a = [a]Source

# The construction and test for ordered lists

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

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] -> BoolSource

Checks if the given argument is ordered.

# The empty list

Returns the empty list `[]`, i.e.

``` > Olist.empty
[]
```

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

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 -> BoolSource

For example,

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

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

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 aSource

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 -> BoolSource

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
```

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 -> BoolSource

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
```

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 -> BoolSource

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

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

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 aSource

The implementation of ∩, for example

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

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

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 aSource

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 aSource

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 []
[]
```

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
```