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 data type into the

`State`monad (as we did with the

`Map`data type for our Ackermann monad optimization):

dataMem=Mem[Integer]InttypeFibS=State Mem Integer

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

fib' ::Int→FibS

fib' n | n ≡ 0 =return0

| n ≡ 1 =return1

|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(Memlst len) ← get

put (Mem(n:lst) (len + 1))

returnn

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 =Justh

| len > n =letx = (len - 1) - n

inJust(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.

## 4 comments:

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

@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

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

Oes Tsetnoc Seo Contest one of the ways in which we can learn seo besides Upaya Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa page and other update like as Beratnya Mengembalikan Jati Diri Bangsa, Mengembalikan Jati Diri Bangsa di perpanjang and Jangan Berhenti Mengembalikan Jati Diri Bangsa. Thank you So much.

Oes Tsetnoc | Lanjutkan Mengembalikan Jati Diri Bangsa

Post a Comment