The Fibonacci series goes as follows: 0,1,1,2,3,5,8,13..., or put another way, the current number is obtained by adding the previous two numbers. It is useful for many things, as its limit is the golden ratio, found in nature (the spiral of some crustaceans and the population growth of rabbits [they must be stopped!]) and in artifice (windows, painting, doors, buildings follow the width and height of this ratio)).
Any fibonacci number can be easily computed from the following formula ...
fib :: Integer → Integer
fib n | n ≡ 0 = 0
| n ≡ 1 = 1
| otherwise = fib (n-1) + fib (n-2)
... that is, easily computed if this world were purely mathematical, including the caveat that any computable function could be instantly computed. Run on a computer,
fib 25slows noticeably and
fib 50may as well describe the halting problem, because I wasn't going to wait around for it to terminate.
Note the similarity between the computation of the Fibonacci series to the computation of the Ackermann table. They are not the same kind of problem, mind you, as the Ackermann is not primitively recursive; the Fibonacci is "only" doubly (branching) recursive. But they are similar enough in that they can be solved in similar ways. Given that the current Fibonacci number is the sum of the previous two Fibonacci numbers, we need only a (reversed) list to memoize the previous results, so the above sequence becomes:
[..., 13, 8, 5, 3, 2, 1, 1, 0]
and the "next" Fibonacci number would be simply the first two elements of this list (21, in this case). But how do we know where we are in the sequence? Easy: the length of this list tells us where we are, and in this case, the list has 8 elements, meaning the "next" Fib is 9th in the sequence.
So, turning to monads with this list structure for memoization, the code falls out as follows:
fib :: Int → FibS
fib n = get >>= λmem . maybe (fib' n >>= update)
(gimme mem n)
fibis now simply a decision: "Do I have the fib requested in the list?" "Yes:
gimmeit and return it" or "No: compute it and then
The list is a very slight variation on a regular list type, as we choose to carry around its length (as opposed to recomputing it at each iteration), and we lift this new data type into the State monad (as we did with the Map data type for our Ackermann monad optimization):
data Mem = Mem [Integer] Int
type FibS = State Mem Integer
The actual computation function is lifted into the monadic form with very little variation ...
fib' :: Int → FibS
fib' n | n ≡ 0 = return 0
| n ≡ 1 = return 1
| otherwise = liftM2 (+) (fib (n - 1)) (fib (n - 2))
... where monadic addition,
liftM2 (+), replaces addition in the usual sense (recall the spot of bother we had "adding" Thing One to Thing Two), and where the plain numbers are lifted into the monad with return. In brief, the substance is now monadic but the structure is the same as our original, plain,
The other housekeeping functions are new for the monadic solution, but what one would expect. The
updatefollows in the same vein as the one for the ackermann monad:
update :: Integer → FibS
update n = do (Mem lst len) ← get
put (Mem (n:lst) (len + 1))
An interpretation of the
updatefunction is that it is the identity function with the side-effect that it remembers the result that it returns.
The only other function is the self-describing
gimmewhich retrieves a previously-computed fibonacci number from memory:
gimme :: Mem → Int → Maybe Integer
gimme (Mem (h:t) len) n | len ≡ n = Just h
| len > n = let x = (len - 1) - n
in Just (t !! x)
| otherwise = Nothing
gimmefunction uses the Maybe monad and its functionality, saying "If I have the value already computed [If the list length is equal to or greater than the requested index], then return Just that value; otherwise I've got Nothing, so you need to compute that value."
In summary, we've decorated the naïve fibonacci algorithm with some memory and three new functions (one manager and two support functions). What is the payoff?
Ready> fib 1500
Ready> fib 50000
[4 second delay]
Ready> fib 60000
[2.5 second delay]
*** Exception: stack overflow
These results are a great step forward over the naïve
fibimplementation (which essentially froze at
fib 50) and even memoized implementation reported elsewhere (which ran out of memory after
Huzzah! then for efficient program representation in Haskell and monadic code.