Week 39

Exercise Tuesday (25.9.2012)

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.

Design by 1234.info | Modified by Peter Schneider-Kamp | CSS 2.0