Tutorial: Fibonacci - Manhunter07/MFL GitHub Wiki

MFL has a built-in Fibonacci function that is pretty fast and reliable at calculating the n'th resolution of the Fibonacci sequence. But since this is one of the most common and also best ways to visualize the functionality and capability of a functional programming language, we will try to find a good functional approach to an own declaration of such a function.

See also: Functions#declaration

At first, what we need to do is to start declaring a Fibonacci function. Theoretically, we can name it anything we want. In practise however, it is useful to name it either Fibonacci or commonly abbreviated Fib. In this tutorial, we will pick the name Fibonacci to avoid confusions with System.Fib. As parameter we declare X to be a positive integer.

So far, our declaration therefore looks as follows:

function Fibonacci(X: PosInt)

Now comes the more difficult part: The implementation of the function's body. In order to create a proper and organized semantic for the Fibonacci algorithm, we have to set up a result table for different X input arguments and their corresponding function results:

As you can see, Fibonacci(X) results in X for 0 ≤ X ≤ 1 and in Fibonacci(X - 2) + Fibonacci(X - 1) for any X ≥ 2. The latter is called a recursion in which we call our function over from inside itself. This is the usual procedure with which we solve such problems in functional programming, similarly to loops in imperative languages.

If we now transform this into an algorithm, we will eventually get something like:

if X ?= 0 then 0 else (if X ?= 1 then 1 else (Fibonacci(X - 2) + Fibonacci(X - 1)))

Or, if we wish to follow a more general approach for X ∈ {0, 1} we can write it this way:

if (X ?= 0) * (X ?= 1) then X else Fibonacci(X - 2) + Fibonacci(X - 1)

Since we now have both header and footer of our Fibonacci function, all it takes is to finally declare it in our code. We declare a function by putting the function body after the function header, separated by an equals sign. This will make our function look like this:

function Fibonacci(X: PosInt) = if X ?= 0 then 0 else (if X ?= 1 then 1 else (Fibonacci(X - 2) + Fibonacci(X - 1)))

Or, if we decided on using the second approach:

function Fibonacci(X: PosInt) = if (X ?= 0) * (X ?= 1) then X else Fibonacci(X - 2) + Fibonacci(X - 1)

See also: Statements#Non-binary branching

So far, we have been constructing the algorithm by using either one or two if statements. But there is also one other alternative without: Using the (specialized, but shorter and slightly faster) way with a case statement. With it, we are able to write the same logics with even less code, while maintaining better readability:

function Fibonacci(X: PosInt) = case X of 0 then 0, 1 then 1 else Fibonacci(X - 2) + Fibonacci(X - 1)

As you can see, this is the shortest way possible of writing our Fibonacci code without the help of external functions.

In this tutorial we have discussed different approaches on how to implement a Fibonacci function in MFL. These are however mostly sample cases that should not be used to reproduce a more efficient (built-in) functionality like Systen.Fib. It nontheless should display very clearly how language features like conditional branches can be used in any possible way, including a recursive function to solve a math problem.