# Week 50

## Exercise Tuesday (13.12.2011)

1) Give the most general type for the following Haskell functions `f`,
`g`, and `h`. Explain your reasoning.

f x y xs z = f z y (x:xs) x

g x = if True then \y -> y else \xs -> x:xs

h [] z r = z ++ r

h (x:y) z r = x ++ h y z r

2) Define a Haskell function `append` that performs list concatenation,
i.e., that behaves like the built-in function `(++)`. You may only
use pattern matching and constructors like `[]` and `(:)`.
Give a type declaration with the most general type for `append`.

Compare your implementation of `append` to the preceding definition
of `sum` for computing the sum of all elements of the list. What
is the most general type of `sum`? Discuss why certain functions
can be defined on polymorphic lists and others cannot.

3) Define a data structure `Set` for sets of integers with the constructors `Insert`
and `EmptySet`. Do not use built-in types (such as `[a]`) in the definition.

Implement the following functions on this data strucure `Set` and also give their respective
type declarations:

- The function
`memberSet`takes an element`x`and a set`s`and returns`True`if, and only if,`x`is an element of`s`. - The function
`subSet`takes two sets`s1`and`s2`and returns`True`if, and only if,`s1`is a subset of`s2`. - A graph can be represented by a set of edges, i.e., by values of the type
`Set (a, a)`. The function`hasPath`applied to two nodes`m`and`n`and a graph`g`returns`True`if, and only if, there is a path from`m`to`n`in`g`.

For example, in the graph`Insert (1,2) (Insert (2,3) EmptySet)`there is a path from`1`to`3`, but not from`3`to`1`.

4) Define a higher-order function `remove :: (a -> Bool) -> [a] -> [a]`.
The expression `keep f xs` should return a list with those elements `x`
of the list `xs` for which `f x` evaluates to `False`.

For example, the expression `keep (\x -> x > 23) [23,42]` must evaluate
to the list `[23]`.

5) Define a higher-order function `mapF` that take a list of function
`[f1, f2, ..., fk]` and a value `x` and return the list
`[f1 x, f2 x, ..., fk x]`.

For example, the expression `mapF [(*3),\x -> x - 2] 5` should return the
list `[15,3]`.

6) Consider the following data structure for binary trees:

data BinTree a = Nil | Node (BinTree a) a (BinTree a)

Write functions `mapTree :: (a -> b) -> BinTree a -> BinTree b` and
`foldTree :: (b -> a -> b -> b) -> b -> BinTree a -> b` that work
on `BinTree` in the same way that `map` and `fold` work
on (pre-defined) lists.

Use `mapTree` to implement a function that takes a tree of
strings and computes a tree of integers where each node of the new
tree contains the length of the string in the corresponding node of
the original tree.

Use `foldTree` to implement a function that takes a tree of
integers and returns the sum of the squares of all elements.

7) Look at the function `take` and `from`, which take some elements from a list
and create a list, respectively.

take :: Int -> [a] -> [a]

take 0 xs = []

take (n+1) (x:xs) = x:take n xs

from :: Int -> [Int]

from n = n:from (n+1)

Show every step in the (lazy) evaluation of the expression `take 3 (from 8)`.

## Lecture Wednesday (14.12.2011)

The tenth lecture will start with analysis of Haskell programs with respect to space, runtime, and correctness.

##### Topics

space and time consumption, correctness proofs

##### Reading

Lecture Notes in Blackboard (Course Documents), chapter on correctness (Course Documents), chapter on complexity (Course Documents)