Fibonacci numbers (Mercury)

From LiteratePrograms

Jump to: navigation, search
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.


Recursion

The recursive definition can be translated directly into Mercury as follows:

Mercury is descendant of Prolog.

Here you specify relations. Then you specify the modes of in/out combinations of the relation parameters that you will implement and the determinism of the solutions. Then facts and rules.

The determinism possibilities are the following:

  • have exactly one solution, then that mode is deterministic (det);
  • either have no solutions or have one solution, then that mode is semideterministic (semidet);
  • have at least one solution but may have more, then that mode is multisolution (multi);
  • have zero or more solutions, then that mode is nondeterministic (nondet);
  • fail without producing a solution, then that mode has a determinism of failure.
  • If no possible calls to a particular mode of a predicate or function can return to the caller, then that mode has a determinism of erroneous.


This module will implement fibonacci /2 with the function pattern, similar to the predicate pattern but with a more familiar layout. 

<<fibonacci.m>>=
:- module fibonacci.
:- interface.
:- func fibonacci(int) = int.
/* an alternative way, using predicates would be
*       :- pred fibonacci( int, int).
*/
/* mode first_param as input '=' result as output is deterministic (has one solution) 
*/
:- mode fibonacci(in) = out is det.
:- implementation.
:- import_module int.
/* fibonacci(N) = F  implies ( cond_goal -> then_goal
*                             ; cond_goal -> then_goal
*                             ; else_goal
*                             )
*/
fibonacci(N) = F   :-   ( N = 0 -> F = 0 
                        ;
                          N = 1 -> F = 1 
                        ;
                          /* else */
                          F = fibonacci(N - 1) + fibonacci(N - 2) 
                        ).

Test module: 

<<fibotest.m>>=
:- module fibotest.
:- interface.
:- import_module io.
:- pred main(io.state, io.state).
:- mode main(di, uo) is det.
:- implementation.
:- import_module fibonacci.
main -->
	io.write_string("fibonacci(7) = "),
	io.write_int(fibonacci(7)),
	io.nl.

Compilation and run

  1. compile fibonacci.m exporting interfaces (-i)
  2. compile fibotest.m specifying the interfaces used (without extension) 
>mmc -i fibonacci.m
>mmc fibotest.m fibonacci
>
>fibotest
>fibonacci(7) = 13
>

Tail Recursive

<<fibonacci_tr.m>>=
:- module fibonacci_tr.
:- interface.
:- func fibonacci(int) = int.
:- mode fibonacci(in) = out is det.
:- implementation.
:- import_module int.
fibonacci(N) = F  :-   F = fibo_tr( N, 1, 0). 
/* tail recursive private function */
:- func fibo_tr(int, int, int) = int.
:- mode fibo_tr(in, in, in) = out is det.
fibo_tr(N, Next, Result) = F   :-   
      ( N = 0 -> F = Result 
      ;
        /* else */
        F = fibo_tr(N - 1, Result + Next, Next) 
      ).
Download code
Retrieved from "http://literateprograms.org/Fibonacci_numbers_%28Mercury%29"
Views