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