Fib sharing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fib1, fib2 :: Int -> Integer
fib1 n =
    let fibs = map fib' [0..]
        fib' 0 = 0
        fib' 1 = 1
        fib' n = fib1 (n - 1) + fib1 (n - 2)
    in fibs !! n

fib2 =
    let fibs = map fib' [0..]
        fib' 0 = 0
        fib' 1 = 1
        fib' n = fib2 (n - 1) + fib2 (n - 2)
    in \n -> fibs !! n