Week 49

Lecture Tuesday (07.12.2010)

The eigth lecture will focus on declaring new types and determining the most general type of functions. Then we will learn about higher-order functions.

Topics

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

Reading

Lecture Notes in Blackboard (Course Documents)

Exercise Wednesday (08.12.2010)

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 Friday (10.12.2010)

The ninth lecture will discuss lazy evaluation, infinite data structures, and I/O in Haskell.

Topics

lazy evaluation, infinite structures, IO monad

Reading

Lecture Notes in Blackboard (Course Documents)