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

Olist

Contents

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