Week 49

Exercise Tuesday (06.12.2011)

1) The function len for computing the length of a list can be implemented as follows:

len :: [a] -> Int
len xs = len' 0 xs
  where len' n [] = n
        len' n (x:xs) = len' (n+1) xs

Here, we use the auxilliary function len' which has an additional parameter for accumulating the result. The function len' is tail recursive, because the recursive function calls on the right-hand side of its declaration do not occur as arguments to other function. In other words, there is no function symbol above the recursive function call len' (n+1) xs.

Use the technique of tail recursion to implement the following functions in Haskell. Give the type declarations for all main and auxilliary functions.

• fact n computes the factorial of n for all n > 0, i.e., the product of all natural numbers from 1 to n. For example, the expression fact 5 yields the value 120.
• sumsquare xs computes the sum of the squares of all elements in xs. For example, the expression sumsquare [1,2,3] yields the value 14.

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

Lecture Wednesday (07.12.2011)

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)

Lecture Friday (09.12.2011)

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)