Week 49

Lecture Tuesday (01.12.2009)

The seventh lecture will continue with the introduction to Haskell.

Topics

expressions, patterns, types, parametric polymorphism, type declarations

Reading

Lecture Notes in Blackboard (Course Documents)

Exercise Wednesday (02.12.2009)

1) Consider the following Haskell program:

squares 0 = []
squares n = n*n : squares (n-1)

take 0 _ = []
take _ [] = []
take (n+1) (x:xs) = x:take n xs

sum [] = 0
sum (x:xs) = x + sum xs

sumFirst2 (x:y:xs) = x+y
sumFirst2 [x] = x
sumFirst2 [] = 0

sumFirst2' xs = sum (take 2 xs)

The function squares computes the descending list of squares from a given number down to 1. For example, squares 5 computes the list [25,16,9,4,1]. The function take returns the prefix of length n of a list. For exampke, take 3 [7,6,1,2,5,8,9] computes the list [7,6,1] and take3 [2,4] the list [2,4]. The function sum computes the sum of all elements of a list. For example, sum [5,2,7] computes 14.

The functions sumFirst2 and sumFirst2' compute the sum of the first two elements of a list in a different way. Give all steps in the evaluation of the following two expressions:

sumFirst2 (squares 4)

sumFirst2' (squares 4)

Keep in mind that Haskell evaluates equations from top to bottom, the arguments from left to right, and only evaluates arguments if it is necessary for pattern matching. The built-in operations for addition and multiplication always evaluate their arguments.

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

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

Lecture Thursday (03.12.2009)

The eigth lecture will continue with the introduction to Haskell. After discussing pattern matching, we will learn more advanced ways for function declarations.

Topics

algebraic data types, higher-order functions, computing most general types

Reading

Lecture Notes in Blackboard (Course Documents)