|
87
|
1 module Fibonacci where
|
|
|
2 -- Classic imperative Fibonacci
|
|
|
3 -- XXX: This seems to give odd answers! "fib_simple 0" gives 1 when it should be 0 (0-based indexing) or an error (1-based indexing)!
|
|
|
4 fib_simple :: Integer -> Integer
|
|
|
5 fib_simple 0 = 1
|
|
|
6 fib_simple 1 = 1
|
|
|
7 fib_simple x = fib_simple (x - 1) + fib_simple (x - 2)
|
|
|
8
|
|
|
9 -- Fibonacci with tuples and effective caching
|
|
|
10 -- This works by using the parameter as the number of steps and iterating those in the tuple
|
|
|
11 -- Note: We're zero-indexing, so "fib 0" is the first Fibonacci number
|
|
|
12 fib :: Integer -> Integer
|
|
|
13 fib x = fibResult (fibTuple (0, 1, x))
|
|
|
14
|
|
|
15 fibResult :: (Integer, Integer, Integer) -> Integer
|
|
|
16 fibResult (x, y, z) = x
|
|
|
17
|
|
|
18 fibTuple :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
|
|
|
19 fibTuple (x, y, 0) = (x, y, 0)
|
|
|
20 fibTuple (x, y, index) = fibTuple (y, x + y, index -1) |
