# Fibonacci numbers (Alice ML)

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.

## 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>>=
import functor MkRedBlackImpMap 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>>=
fun fib 0 = 0
| fib 1 = 1
| fib n if (n > 1) = fib(n - 1) + fib(n - 2)
| fib _ = raise Domain


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.

fun fib 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 n if (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 _ = raise Domain


We can test the fib function in the following manner:

- [fib 0, fib 1, fib 2, fib 3];
val it : int list = [0, 1, 1, 2]
- fib 7;
val it : 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>>=
local
structure Memo = MkRedBlackImpMap Int
val table = Memo.map()
in
fun memo_fib n =
let
val previously_computed_result = Memo.lookup(table, n)
in
case previously_computed_result of
| SOME item => item
| NONE =>
let
fun fib 0 = 0
| fib 1 = 1
| fib n if (n > 1) = memo_fib(n - 1) + memo_fib(n - 2)
| fib _ = raise Domain
val result = fib n
in
Memo.insert(table, n, result);
result
end
end
end


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;
val it : int = 701408733


## Iteration

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

<<fib.aml>>=
fun iterative_fib n =
let
fun fib (a, b, 0) = b
| fib (a, b, count) if (n > 0) = fib(a + b, a, count - 1)
| fib _ = raise Domain
in
fib(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>>=
fun lazy fibgen (a, b) =
a :: fibgen(b, a + b)
val fibs = 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);
val it : 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>>=
val inf_0 = IntInf.fromInt 0
val inf_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>>=
fun inf_iterative_fib n =
let
fun fib (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 _ = raise Domain
in
fib(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);
val it : IntInf.t = 354224848179261915075