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

Contents 1 Import 2 Recursion 3 Memoize 4 Iteration 5 Streams 6 Unlimited Integer Sizes

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 Φⁿ, 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

Download code