# Fibonacci numbers (Alice ML)

### From LiteratePrograms

**Other implementations**: ALGOL 68 |**Alice ML**| bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by

- 1 \\ \end{cases} ."/>

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.

## Contents |

## Import

Alice ML requires any package imports to be located at the top of a script. We will be using the RedBlack dictionary for the memoization.

<<fib.aml>>=importfunctorMkRedBlackImpMap from "x-alice:/lib/data/MkRedBlackImpMap"

## Recursion

A simple recursive solution can be constructed in Alice ML in a way that directly mirrors the mathematical definition of the function.

<<fib.aml>>=funfib 0 = 0 | fib 1 = 1 | fib nif(n > 1)= fib(n - 1)+ fib(n - 2)| fib _ =raiseDomain

We use pattern matching on the function's parameter to handle the three cases given in the definition of the Fibonacci numbers. The first two cases we handle are the base cases of the recursion, when n = 0 or n = 1.

funfib 0 = 0 | fib 1 = 1

In the third case, when n > 1, a pair of recursive calls are made. The first call determines the F(n-1), and the second determines F(n-2), adding the two values to compute the F(n), the nth Fibonacci number.

| fib nif(n > 1)= fib(n - 1)+ fib(n - 2)

Finally, we add a final case to our pattern matching to catch all other cases. This is done for two reasons. First, Fibonacci numbers are only defined for non-negative integers. While that may be fine in math, when it comes to programming, one should be aware that invalid inputs may be used. These cases should be caught and handled. Here we raise an exception that can be handled by the caller of `ackermann`

. Secondly, when using the guards in pattern matching, Alice ML may be unable to determine if all possible cases are covered, and it issues a warning. Using the universal match pattern, _, we can catch any cases not covered by the above patterns (in this case anything involving negative integers).

| fib _ =raiseDomain

We can test the fib function in the following manner:

-[fib 0, fib 1, fib 2, fib 3];valit : int list =[0, 1, 1, 2]- fib 7;valit : int = 13

## Memoize

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating fib(*n*) requires calculating two smaller Fibonacci numbers, which in turn require two additional recursive calls each, and so on until all branches reach 1. As a consequence, the time required to calculate fib(*n*) is exponential in *n* (it is about Φ^{n}, where Φ is the golden ratio). To remedy this, we can employ memoization to cache previous computations.

<<fib.aml>>=localstructureMemo = MkRedBlackImpMap Intvaltable = Memo.map()infunmemo_fib n =letvalpreviously_computed_result = Memo.lookup(table, n)incasepreviously_computed_resultof| SOME item => item | NONE =>letfunfib 0 = 0 | fib 1 = 1 | fib nif(n > 1)= memo_fib(n - 1)+ memo_fib(n - 2)| fib _ =raiseDomainvalresult = fib ninMemo.insert(table, n, result); resultendendend

The memoized `fib`

function recursively computes and stores the value of `fib(n)`

if it hasn't been previously stored in the `memo`

dictionary. Otherwise it simply returns the memoized value of `fib(n)`

.

With the memoized version, larger Fibonacci numbers can be found in no time:

- memo_fib 44;valit : int = 701408733

## Iteration

To calculate the *n*th Fibonacci number in only *n* steps, we can also start with 0 and 1 and iteratively add up items *n* times:

<<fib.aml>>=funiterative_fib n =letfunfib(a, b, 0)= b | fib(a, b, count)if(n > 0)= fib(a + b, a, count - 1)| fib _ =raiseDomaininfib(1, 0, n)end

## Streams

One can also use streams in Alice ML to build the Fibonacci numbers in a lazy fashion. The Fibonacci sequence can be defined as a function that takes in the ith and i+1st Fibonacci numbers and returns an infinite stream of Fibonacci numbers starting from i.

<<fib.aml>>=funlazy fibgen(a, b)= a :: fibgen(b, a + b)valfibs = fibgen(0, 1)

To get the 40th number in the sequence, we can pull it from the list in the following manner:

- List.nth(fibs, 40);valit : int = 102334155

## Unlimited Integer Sizes

The standard size of an integer in Alice ML is restricted to 31 bits (Int.minInt = ~1073741824 to Int.maxInt = 1073741823). In order to handle numbers outside of this range, the type for the numbers should be changed to IntInf. Since Alice ML doesn't currently support IntInf constants, we'll declare some values to hold 0 and 1.

<<fib.aml>>=valinf_0 = IntInf.fromInt 0valinf_1 = IntInf.fromInt 1

Since we are interested in large values, we'll use the iterative version of fib to showcase how to write a fib function using infinite integers:

<<fib.aml>>=funinf_iterative_fib n =letfunfib(a, b, count)if(count = inf_0)= b : IntInf.t | fib(a, b, count)if(count > inf_0)= fib(a + b, a, count - inf_1)| fib _ =raiseDomaininfib(inf_1, inf_0, n)end

The inf_ackermann allows us to compute results with a large number of digits:

- inf_iterative_fib(IntInf.fromInt 100);valit : IntInf.t = 354224848179261915075

Download code |