Haskell/Solutions/Recursion

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

← Back to Recursion


[edit] The factorial function

Exercises
  1. Type the factorial function into a Haskell source file and load it into your favourite Haskell environment.
    • What is factorial 5?
    • What about factorial 1000? If you have a scientific calculator (that isn't your computer), try it there first. Does Haskell give you what you expected?
    • What about factorial (-1)? Why does this happen?
  2. 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.
    • It's 120.
    • The scientific calculator probably gives a memory error (if not, tell me which one you use!). Haskell returns it just fine, since Haskell can use arbitrary-precision integers. We won't show it here, though, since it contains 2568 digits!
    • 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), which is... obviously, this never stops, so it will keep going until it runs out of memory. In the chapter on Control structures we will see how to fix this.
  2. doublefactorial can be defined as follows:
doublefactorial 0 = 1
doublefactorial 1 = 1
doublefactorial n = n * doublefactorial (n-2)

[edit] Other recursive functions

Exercises
  1. Expand out the multiplication 5 × 4 similarly to the expansion we used above for factorial 3.
  2. Define a recursive function power such that power x y raises x to the y power.
  3. 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.
  4. 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

[edit] 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.

  1. 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. replicate 'a' 3 = "aaa". (Hint: think about what replicate of anything with a count of 0 should be; a count of 0 is your 'base case'.)
  2. (!!) :: [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 recursing both numerically and down a list.
  3. (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')].

The answers, in one block of code:

replicate 0 thing  = []
replicate n thing = thing : replicate (n-1) thing 

(x:xs) !! 0 = x
(x:xs) !! n = xs !! (n-1)
--note that an error occurs when the list is too short.
--For example: "abc" !! 3 gives an "index too large" exception.

zip []     list   = []
zip list   []     = []
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 _      _      = []
Retrieved from "http://en.wikibooks.org/wiki/Haskell/Solutions/Recursion"