Skip to content

Instantly share code, notes, and snippets.

@morgaine
Last active September 17, 2019 18:28
Show Gist options
  • Save morgaine/cb8df3299a62d75b302fb10d9a51d2cb to your computer and use it in GitHub Desktop.
Save morgaine/cb8df3299a62d75b302fb10d9a51d2cb to your computer and use it in GitHub Desktop.
Fibonacci in Erlang, multiple algorithms, commandline interface
#! /bin/env escript
% NAME
% fib_multi.erl -- Multiple algorithms for Fibonacci numbers
%
% SYNOPSIS
% fib_multi {from-integer} [{to-integer}]
%
% INSTALL
% ln -s fib_multi.erl fib_multi
%
% DESCRIPTION
% FutureLean course "Functional Programming in Erlang".
% Lesson 1.23 (part of)
% Pattern matching revisted
%
% Exercise extended a little with:
% 1) use of "escript" from the commandline,
% 2) generation and display of Fib sequence from N to M,
% 3) ourputs direct, tail-recursive and tupled algorithms
% 4) generation of Fib sequence list using seq and map
% 5) formatting exercise with io:format and io_lib:format.
%
% Because of the 2 terms of sequence history that are being used,
% termination of the tail-recursive function is not very obvious.
% The step-by-step evaluation actually helped pin down termination
% in this case, which was complicated by use of N simultaneously
% as a loop downcounter and as the argument to fib_tail(N).
% The walkthrough also showed that a superfluous loop was being
% performed and a computation wasted, fixed with N=1 boundary case.
%
% Step-by-step evaluation of the tuple-valued direct recursive was
% very interesting but excessively complex, and hence should not be
% used as a development M.O. as it would introduce errors. IMO this
% type of algorithm must be designed and analysed only declaratively.
% As in the case of the tail-recursive solution, the walkthrough
% showed that a superfluous loop was being performed and a computation
% wasted. This was once again fixed by adding an N=1 boundary case.
%
% STEP BY STEP EVALUATION OF fib(4)
% fib(4) = fib(2) + fib(3)
% = (fib(0) + fib(1)) + (fib(1) + fib(2))
% = (0 + 1) + (1 + (fib(0) + fib(1)))
% = 1 + (1 + (0 + 1))
% = 1 + (1 + 1)
% = 1 + 2
% = 3
%
% STEP BY STEP EVALUATION OF fib_tail(4) prior to adding N=1 boundary case:
% fib_tail(4) = fib_tail(0, 1, 4)
% = fib_tail(1, 0+1, 3) = fib_tail(1, 1, 3)
% = fib_tail(1, 1+1, 2) = fib_tail(1, 2, 2)
% = fib_tail(2, 1+2, 1) = fib_tail(2, 3, 1)
% = fib_tail(3, 2+3, 0) = fib_tail(3, 5, 0) %% Superfluous computation
% = 3
%
% STEP BY STEP EVALUATION OF fib_tupled(4) prior to adding N=1 boundary case:
% fib_tupled(4) = {P,_} = fib_tuple(4),
% P
% = {P,_} = ({P,C} = fib_tuple(3),
% {C, P+C}),
% P
% = {P,_} = ({P,C} = ({P,C} = fib_tuple(2),
% {C, P+C}),
% {C, P+C}),
% P
% = {P,_} = ({P,C} = ({P,C} = ({P,C} = fib_tuple(1),
% {C, P+C}),
% {C, P+C}),
% {C, P+C}),
% P
% = {P,_} = ({P,C} = ({P,C} = ({P,C} = ({P,C} = fib_tuple(0),
% {C, P+C}),
% {C, P+C}),
% {C, P+C}),
% {C, P+C}),
% P
% = {P,_} = ({P,C} = ({P,C} = ({P,C} = ({P,C} = {0,1},
% {C, P+C}),
% {C, P+C}),
% {C, P+C}),
% {C, P+C}),
% P
% = {P,_} = ({P,C} = ({P,C} = ({P,C} = {1, 0+1},
% {C, P+C}),
% {C, P+C}),
% {C, P+C}),
% P
% = {P,_} = ({P,C} = ({P,C} = {1, 1+1},
% {C, P+C}),
% {C, P+C}),
% P
% = {P,_} = {3, 2+3}, %% Superfluous computation
% P
% = 3
%
% TODO
% Validity of numeric commandline arguments is not yet checked.
-module(fib).
-export([fib/1, fibShow/1, fibShow/2, fibList/2]).
% ----- Algorithm 1: simple direct recursion, highly declarative
% Direct recursive term generator function for the Fibonacci Sequence.
% Generates the Nth term of the Fibonacci sequence starting from 0.
fib(0) ->
0;
fib(1) ->
1;
fib(N) ->
fib(N-2) + fib(N-1).
% ----- Algorithm 2: tail recursion with dual accumulators
% Tail-recursive generator function for the Fibonacci Sequence.
% Generates the Nth term of the Fibonacci sequence starting from 0.
fib_tail(N) when N >= 0 ->
fib_tail(0, 1, N).
% The separate termination condition for a downcount to 1 prevents a
% final superfluous iteration from occurring, only to be discarded on 0.
% See "% STEP BY STEP EVALUATION OF fib_tail(4)" in the header above.
fib_tail(Old, _, 0) ->
Old;
fib_tail(_, New, 1) -> %% N=1 case to prevent executing but discarding computation
New;
fib_tail(Old, New, DountCount) ->
fib_tail(New, Old+New, DountCount-1).
% ----- Algorithm 3: return adjacent Fibonacci pairs
fib_tuple(0) ->
{0,1};
fib_tuple(1) -> %% N=1 case to prevent executing but discarding computation
{1,1};
fib_tuple(N) ->
{Prev, Curr} = fib_tuple(N-1),
{Curr, Prev+Curr}.
fib_tupled(N) ->
{Prev,_} = fib_tuple(N),
Prev.
% --------------
% Calculate padding width to even out growth in fib input and output up to 6 digits wide.
wid(X,Y) ->
[C1,C2] = io_lib:format("~p~p", [X,Y]),
8 - length(C1++C2).
% Two alternative ways of printing numbers for individual preference, "~Nw" and "~*c".
fibShow(N) ->
%% If you prefer right-aligned numbers, set the first guard to 'true'.
if
false -> fibShow1(N);
true -> fibShow2(N)
end.
fibShow1(N) ->
% io:format("fib(~p) = ~p, fib_tail(~p) = ~p, fib_tupled(~p) = ~p~n", [ N, fib(N), N, fib_tail(N), N, fib_tupled(N) ]).
io:format("fib(~2w) = ~6w, fib_tail(~2w) = ~6w, fib_tupled(~2w) = ~6w~n", [ N, fib(N), N, fib_tail(N), N, fib_tupled(N) ]).
fibShow2(N) ->
F1 = fib(N),
F2 = fib_tail(N),
io:format("fib(~p) = ~w, ~*cfib_tail(~p) = ~w, ~*cfib_tupled(~p) = ~w~n", [
N, fib(N), wid(N,F1), 32,
N, fib_tail(N), wid(N,F2), 32,
N, fib_tupled(N)
]).
fibShow(N,N) ->
fibShow(N);
fibShow(N,M) when N =< M ->
fibShow(N,M-1),
fibShow(M,M);
fibShow(N,M) ->
io:format("fib_multi: ERROR: to-integer ~p is smaller than from-integer ~p~n", [M,N]),
halt(2).
fibList(N,M) when N =< M ->
lists:map(fib/1, lists:seq(N,M)).
main() ->
io:format("Usage: fib_multi {from-integer} [{to-integer}]~n"),
halt(1).
main([]) ->
main();
main([NumericString]) ->
N = list_to_integer(NumericString),
fibShow(N);
main([FromNumber, ToNumber]) ->
N = list_to_integer(FromNumber),
M = list_to_integer(ToNumber),
fibShow(N,M);
main([_,_,_|_]) ->
io:format("Too many arguments.~n"),
main().
@morgaine
Copy link
Author

morgaine commented Feb 24, 2017

Example usage from commandline:

$ ./fib_multi
Usage: fib_multi {from-integer} [{to-integer}]
$ ./fib_multi 0 12
fib(0) = 0,       fib_tail(0) = 0,       fib_tupled(0) = 0
fib(1) = 1,       fib_tail(1) = 1,       fib_tupled(1) = 1
fib(2) = 1,       fib_tail(2) = 1,       fib_tupled(2) = 1
fib(3) = 2,       fib_tail(3) = 2,       fib_tupled(3) = 2
fib(4) = 3,       fib_tail(4) = 3,       fib_tupled(4) = 3
fib(5) = 5,       fib_tail(5) = 5,       fib_tupled(5) = 5
fib(6) = 8,       fib_tail(6) = 8,       fib_tupled(6) = 8
fib(7) = 13,      fib_tail(7) = 13,      fib_tupled(7) = 13
fib(8) = 21,      fib_tail(8) = 21,      fib_tupled(8) = 21
fib(9) = 34,      fib_tail(9) = 34,      fib_tupled(9) = 34
fib(10) = 55,     fib_tail(10) = 55,     fib_tupled(10) = 55
fib(11) = 89,     fib_tail(11) = 89,     fib_tupled(11) = 89
fib(12) = 144,    fib_tail(12) = 144,    fib_tupled(12) = 144

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment