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*) and in artifice (windows, painting, doors, buildings follow the width and height of this ratio)).

__must__be stopped!]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 25`

slows noticeably and `fib 50`

may 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)

return

(gimme mem n)

So,

`fib`

is now simply a decision: "Do I have the fib requested in the list?" "Yes: `gimme`

it and `return`

it" or "No: compute it and then `update`

the list"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 datatype into the

`State`

monad (as we did with the `Map`

datatype 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, `fib`

.The other housekeeping functions are new for the monadic solution, but what one would expect. The

`update`

follows 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))

return n

An interpretation of the

`update`

function is that it is the identity function with the side-effect that it remembers the result that it `return`

s.The only other function is the self-describing

`gimme`

which 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

This

`gimme`

function 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[no delay]

135511256685631019516369368671484083777860107124184972421335

431532214873108735287506122593540357172653003737788143473202

576992570823565500453499141029242495959974839822286992875272

419318113250950996424476212422002092544399201969604653214384

983053458933789325853933815390935494792961948008381459961871

22583354898000

Ready> fib 50000[4 second delay][10615 digits]

Ready> fib 60000[2.5 second delay]

*** Exception: stack overflow

These results are a great step forward over the naïve

`fib`

implementation (which essentially froze at `fib 50`

) and even memoized implementation reported elsewhere (which ran out of memory after `fib 1450`

).Huzzah! then for efficient program representation in Haskell and monadic code.

## No comments:

Post a Comment