Info SPLib Functions

SPLib.Basic

if'
 Bool -> a -> a -> a
x y z returns y if x is true, else z
id
 a -> a
x x (identity)
show
 a -> String
x converts x into a string
read
 String -> a
x converts a string x back into a value of type a.
The return type has to be specified explicitly, e.g. (read "[1,2,3]")::[Int]
trace
 String -> a -> a
x y prints x to the console (stderr) and returns y
++
 [a] -> [a] -> [a]
lst1 lst2 appends lst2 to lst1, e.g. [1,2]++[3,4] = [1,2,3,4]
.
 (b -> c) -> (a -> b) -> (a -> c)
f g maps x to (f (g x)) (composition)

fst
 (a,b) -> a
(x,y) x (first component of a tuple)
snd
 (a,b) -> b
(x,y) y (second component of a tuple)

&&
 Bool -> Bool -> Bool
a b a && b (conjunction)
||
 Bool -> Bool -> Bool
a b a || b (disjunction)
not
 Bool -> Bool
a negation of a

==
 a -> a -> Bool
x y x == y (equality)
/=
 a -> a -> Bool
x y x /= y (inequality)
<
 a -> a -> Bool
x y x < y
<=
 a -> a -> Bool
x y x <= y
>
 a -> a -> Bool
x y x > y
>=
 a -> a -> Bool
x y x >= y

+
 Int -> Int -> Int
a b a + b
-
 Int -> Int -> Int
a b a - b
*
 Int -> Int -> Int
a b a * b
^
 Int -> Int -> Int
a b a ^ b (exponentiation)
div
 Int -> Int -> Int
a b how many times does b go into a (integer division)
mod
 Int -> Int -> Int
a b rest after dividing a by b (modulo)
min
 Int -> Int -> Int
a b returns a if a < b, else b
max
 Int -> Int -> Int
a b returns a if a > b, else b
succ
 Int -> Int
x x+1
pred
 Int -> Int
x x-1

SPLib.List

isEmpty
 [a] -> Bool
lst returns True if lst is empty
length
 [a] -> Int
lst number of elements in lst

get
 Int -> [a] -> a
i lst returns element with index i in lst; the first element has index 0
first
 [a] -> a
lst returns first element in lst
last
 [a] -> a
lst returns last element in lst

set
 a -> Int -> [a] -> [a]
el i lst sets element with index i in lst to el
prepend
 a -> [a] -> [a]
el lst prepends el to lst
append
 a -> [a] -> [a]
el lst appends el to lst
insert
 a -> Int -> [a] -> [a]
el i lst inserts el in lst such that it has index i in the returned list

remove
 Int -> [a] -> [a]
i lst removes element with index i from lst
removeFirst
 [a] -> [a]
lst removes first element from lst
removeLast
 [a] -> [a]
lst removes last element from lst

take
 Int -> [a] -> [a]
n lst returns first n elements from lst. If lst has fewer than n elements then lst is returned
drop
 Int -> [a] -> [a]
n lst removes the first n elements from lst. If lst has fewer than n elements then the empty list is returned

reverse
 [a] -> [a]
lst reverses the order of the elements in lst
sort
 [a] -> [a]
lst sorts the elements in lst
sortBy
 (a -> a -> Ordering) -> [a] -> [a]
f lst sorts the elements in lst w.r.t. the order which is specified by f

concat
 [[a]] -> [a]
lst concatenates the lists in lst, e.g. concat [a,b,c] = a ++ b ++ c
zip
 [a] -> [b] -> [(a,b)]
lst1 lst2 pairs the elements of the two list pairwise, e.g. zip [1,2,3] ['a','b','c'] = [(1,'a'),(2,'b'),(3,'c')].
If one list is shorter than the other than the excess elements in the larger list are ignored

map
 (a -> b) -> [a] -> [b]
f lst applies f to each element of lst, e.g. map f [1,2,3] = [(f 1), (f 2), (f 3)]
filter
 (a -> Bool) -> [a] -> [a]
f lst removes all elements x from lst for which (f x) == False
reduce
 (a -> a -> a) -> [a] -> a
f lst assume lst=[x1,x2,x3], then (f (f x1 x2) x3) is returned.
If lst consists of only one element then this element is returned. Undefined if lst is empty.
foldl
 (b -> a -> b) -> b -> [a] -> b
f acc lst assume lst=[x1,x2,x3], then (f (f (f acc x1) x2) x3) is returned.
If lst is empty then acc is returned. This is a generalized version of the function reduce
foldr
 (a -> b -> b) -> b -> [a] -> b
f acc lst assume lst=[x1,x2,x3], then (f x1 (f x2 (f x3 acc))) is returned.
If lst is empty then acc is returned
find
 (a -> Bool) -> [a] -> a
f lst returns the first element x in lst for which f x == True holds. This function is undefined if no such element exists

SPLib.Map

isEmpty
 (Map k v) -> Bool
m returns True iff m is empty
size
 (Map k v) -> Int
m returns number of elements in m

empty
 (Map k v)
returns an empty map
fromList
 [(k,v)] -> (Map k v)
lst converts lst into a map. If a key occurs more than once then the last value is taken
toList
 (Map k v) -> [(k,v)]
m converts m into a list of tuples

hasKey
 k -> (Map k v) -> Bool
key m returns True iff m contains the key key
get
 k -> (Map k v) -> v
key m returns the value in m that is associated with the key key. Undefinded if the key does not exist
set
 v -> k -> (Map k v) -> (Map k v)
val key m sets the value associated with the key in m to val
remove
 k -> (Map k v) -> (Map k v)
key m removes the key-value-pair with key key from m

SPLib.Tree

Note: a node v is encoded as a list of Int (type Path = [Int]) which describe the path to that node. Examples:

allNodes
 (Tree a) -> [Path]
tree returns a list of all nodes of tree
size
 (Tree a) -> Int
tree returns the number of nodes in tree
degree
 Path -> (Tree a) -> Int
v tree returns the number of children of v in tree
pathExists
 Path -> (Tree a) -> Bool
v tree returns True iff tree has a node at path v

getLabel
 Path -> (Tree a) -> a
v tree returns the label of node v in tree
setLabel
 a -> Path -> (Tree a) -> (Tree a)
label v tree sets the label of node v in tree to label

rootLabel
 (Tree a) -> a
tree returns the label of the root node in tree
rootDegree
 (Tree a) -> Int
tree returns the number of children of the root node in tree

subtree
 Path -> (Tree a) -> (Tree a)
v tree returns the subtree of tree which starts at node v
appendSubtree
 (Tree a) -> Path -> (Tree a) -> (Tree a)
subtree v tree appends the tree subtree to the children of v in tree