## Wednesday, May 14, 2008

### No "fib"bing; getting into the monad groove

The title is groan-inducing, as all my "jokes" are. I guarantee it: once you've finished reading this entry, reread the title, and you won't be able to stop from groaning.

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 → Integerfib 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 → FibSfib 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 data type into the State monad (as we did with the Map data type for our Ackermann monad optimization):

`data Mem = Mem [Integer] Inttype FibS = State Mem Integer`

The actual computation function is lifted into the monadic form with very little variation ...

`fib' :: Int → FibSfib' 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 → FibSupdate 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 returns.

The only other function is the self-describing `gimme` which retrieves a previously-computed fibonacci number from memory:

`gimme :: Mem → Int → Maybe Integergimme (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]13551125668563101951636936867148408377786010712418497242133543153221487310873528750612259354035717265300373778814347320257699257082356550045349914102924249595997483982228699287527241931811325095099642447621242200209254439920196960465321438498305345893378932585393381539093549479296194800838145996187122583354898000Ready> 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`).

Pete Kazmier said...

I'm sure you've seen this before, but I am always impressed with this Haskell implementation of the Fibonacci series.

> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Finding the nth number in the series is a simple matter of:

> fibs !! 50000

Shin no Noir said...

@pete kazmier:
While that definition works, you cannot use the index operator for large indices (because of lazy evaluation).

The solution is to force the evaluation of the preceding elements. For example:

-- 1-based strict indexing for infinite lists.
xs !!! n = foldl1' seq \$ take n xs

ghkj said...

However mean your gold in wow life is,buy wow gold meet it and live it ;wow gold cheap do not shun it and call it hard names.It is not so bad as you are.It looks poorest when you are richest.The fault-finder will find faults in paradise.wow gold kaufen love your life,poor as it is.maple meso You may perhaps have some pleasant,thrilling,maplestory power leveling glorious hourss,even in a poor-house.The setting sun is reflected from the windows of the alms-house as brightly as from the rich man's abode;the snow melts before its door as early in the spring.sell wow gold I do not see but a quiet mind may live as contentedly there,cheap mesos and have as cheering thoughts,as in a palace.The town's poor seem to me often to live the most independent lives of any.May be they are simply great enough to billig wow gold receive without misgiving.Most think that they are above being supported by the town;powerlevel but it often happens that buy maplestory mesos they are not above supporting themselves by dishonest means.which should be more disreputable.Cultivate poverty like a garden herb,like sage.Do not trouble wow powerleveln yourself much to get new things,maple mesos whether clothes or friends