# 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.