Haskell/Solutions/Recursion

The factorial function

Exercises

Type the factorial function into a Haskell source file and load it into GHCi.
Try examples like factorial 5 and factorial 1000.
- What about factorial (-1)? Why does this happen?
The double factorial of a number n is the product of every other number from 1 (or 2) up to n. For example, the double factorial of 8 is 8 × 6 × 4 × 2 = 384, and the double factorial of 7 is 7 × 5 × 3 × 1 = 105. Define a doubleFactorial function in Haskell.

factorial can be defined as follows:

factorial 0 = 1
factorial n = n * factorial(n - 1)

Typing factorial (-1) should yield the message *** Exception: stack overflow. This is because, according to the definition, factorial (-1) is (-1) * factorial (-2), which is (-1) * (-2) * factorial (-3). This will never stop, so the function will keep going until it runs out of memory.
doubleFactorial can be defined as follows:

doubleFactorial 0 = 1
doubleFactorial 1 = 1
doubleFactorial n = n * doubleFactorial (n-2)

Other recursive functions

Exercises

Expand out the multiplication 5 × 4 similarly to the expansion we used above for factorial 3.
Define a recursive function power such that power x y raises x to the y power.
You are given a function plusOne x = x + 1. Without using any other (+)s, define a recursive function addition such that addition x y adds x and y together.
(Harder) Implement the function log2, which computes the integer log (base 2) of its argument. That is, log2 computes the exponent of the largest power of 2 which is less than or equal to its argument. For example, log2 16 = 4, log2 11 = 3, and log2 1 = 0. (Small hint: read the last phrase of the paragraph immediately preceding these exercises.)

1. 5 × 4:

4 isn't 1, so we recurse: work out 5 × 3

3 isn't 1, so we recurse

2 isn't 1, so we recurse

1 is 1, so we return 5

We add the current number, 5, to the result of the recursion, 5. We get 10

We add the current number, 5, to the result of the recursion, 10. We get 15

We add the current number, 5, to the result of the recursion, 15. We get 20.

2.

power x 0 = 1
power x y = x * power x (y-1)

3.

addition x 0 = x
addition x y = plusOne (addition x (y-1))

4.

log2 1 = 0
log2 n = 1 + log2 (n `div` 2) -- the "`" make div into infix notation

List-based recursion

Exercises

Give recursive definitions for the following list-based functions. In each case, think what the base case would be, then think what the general case would look like, in terms of everything smaller than it.

replicate :: Int -> a -> [a], which takes an element and a count and returns the list which is that element repeated that many times. E.g. replicat 3 'a' = "aaa". (Hint: think about what replicate of anything with a count of 0 should be; a count of 0 is your 'base case'.)
(!!) :: [a] -> Int -> a, which returns the element at the given 'index'. The first element is at index 0, the second at index 1, and so on. Note that with this function, you're recurring both numerically and down a list.
(A bit harder.) zip :: [a] -> [b] -> [(a, b)], which takes two lists and 'zips' them together, so that the first pair in the resulting list is the first two elements of the two lists, and so on. E.g. zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')]. If either of the lists is shorter than the other, you can stop once either list runs out. E.g. zip [1,2] "abc" = [(1, 'a'), (2, 'b')].
Define length using an auxiliary function and an accumulating parameter, as in the loop-like alternate version of factorial.

The answers for 1-3, in one block of code:

replicat 0 _     = []
replicat n thing = thing : replicat (n-1) thing

[]     !! _ = error "Index too large" -- An empty list has no elements.
(x:_)  !! 0 = x
(x:xs) !! n = xs !! (n-1)

zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

(x:xs) does not match on an empty list so you can also have:

zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _      _      = []

And here is the accumulating length:

length xs = go 0 xs
    where
    go acc []     = acc
    go acc (_:xs) = go (acc + 1) xs