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)