Week 50

Lecture Tuesday (14.12.2010)

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)

Exercise Wednesday (15.12.2010)

1) 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.

2) 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].

3) 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].

4) 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.

Exercise Friday (17.12.2010)

1) 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).

2) To represent graphs we can use finite lists of pairs of nodes. Each pair represents an edge between two nodes:

type Graph a = [(a,a)]

Consider the graph g over integers above. A representation of g as an object of type Graph Int could be:

[(0,1),(1,3),(3,1),(0,2),(1,0),(2,2)]

The following data structure represents trees where every node may have an arbitrary number of children:

data Tree a = Node a [Tree a]

Consider the tree t above that is the result of unfolding the graph g starting from 0. A representation of the first four layers of the infinite tree t as an object of type Tree Int in Haskell could be:

Node 0 [Node 1 [Node 3 [Node 1 [..., ...]], Node 0 [Node 1 [..., ...], Node 2 [...]], Node 2 [Node 2 [Node 2 [...]]]

Implement the following functions in Haskell:

• The function unfold takes a graph g and a node x and returns the tree which results from unfolding g starting from x. Note that for a cyclic graph, the tree can be infinite.
• The function pruneTree :: Tree a -> Int -> Tree a takes a tree t and an integer n and returns the first n layers of the tree. This corresponds to the function take on lists. For example, the expression pruneTree (unfold [(0,1),(1,3),(3,1),(0,2),(1,0),(2,2)] 0) 4 should evaluate to the expression Node 0 [Node 1 [Node 3 [Node 1 []], Node 0 [Node 1 [], Node 2[]]], Node 2 [Node 2 [Node 2 []]].

3) The two functions fibs1 and fibs2 compute the infinite list of Fibonacci numbers starting from 0 and 1, i.e., the list [0,1,1,2,3,5,8,13,21,34,55,...]. The Fibonacci sequence fib₀, fib₁, ... is defined by fib₀ = 0, fib₁ = 1, and fib_n+2 = fib_n+1 + fib_n.

fibs1 = map fib [0..] where
    fib 0 = 0
    fib 1 = 1
    fib (n+2) = (fib (n+1)) + (fib n)

fibs2 = map fib [0..] where
    fib n = fib' n 0 1 where
        fib' n a b | n == 0 = a
                   | True   = fib' (n-1) (a+b) a

Analyze the complexity of evaluating the two expressions take n fibs1 and take n fib2 depending on n. Give upper bounds using the O-notation that are as low as possible. Here, you can assume that addition has constant complexity, i.e., evaluating n + m is in O(1).

Implement a function fibs3 which computes the same list as fibs1 and fibs2 by using a cyclic data structure. Analyze the complexity of evaluating take n fibs3 depending on n as before.

To measure the amount of reductions, in hugs you can type :s +s to switch on the "profiler". This might give you an idea of the behaviour for different n.