The factorial functionEdit
- 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!
factorial (-1)should yield the message
*** Exception: stack overflow. This is because, according to the definition,
(-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.
doublefactorialcan be defined as follows:
doublefactorial 0 = 1 doublefactorial 1 = 1 doublefactorial n = n * doublefactorial (n-2)
Other recursive functionsEdit
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.
power x 0 = 1 power x y = x * power x (y-1)
addition x 0 = x addition x y = plusOne (addition x (y-1))
log2 1 = 0 log2 n = 1 + log2 (n `div` 2) -- the "`" make div into infix notation
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.
The answers, 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 _ _ =