Skip to content

Instantly share code, notes, and snippets.

@mareknowak
Last active May 9, 2020 03:27
Show Gist options
  • Save mareknowak/22f5dc1b9fa7c665281f1a592633e476 to your computer and use it in GitHub Desktop.
Save mareknowak/22f5dc1b9fa7c665281f1a592633e476 to your computer and use it in GitHub Desktop.
Tail recursion - FP in Erlang 2.5
%% @doc Tail recursion - FP in Erlang 2.5
-module(tail).
-export([sum/2, maximum/2, fib/1, perfect/1, test/0]).
%% @doc Given a function (Fun: int -> int) and an integer N,
%% find the value of Fun(N) + Fun(N - 1) + ... + Fun(0).
%%
%% sum_aux is auxiliary function keeping a current Sum value
sum_aux(0, _, Total) ->
Total;
sum_aux(N, Fun, Sum) when N > 0 ->
sum_aux(N - 1, Fun, Sum + Fun(N)).
sum(N, F) ->
sum_aux(N, F, 0).
test_sum() ->
6 = tail:sum(3, fun (X) -> X end),
14 = tail:sum(3, fun (X) -> X * X end),
ok.
%% @doc Given a function (Fun: int -> int) and an integer N,
%% find the largest value Fun(N), Fun(N - 1) ,... ,Fun(0).
%%
%% maximum_aux is auxiliary function keeping a current Max value
maximum_aux(0, Fun, Max) ->
max(Max, Fun(0));
maximum_aux(N, Fun, Max) when N > 0 ->
maximum_aux(N - 1, Fun, max(Max, Fun(N - 1))).
maximum(N, F) ->
maximum_aux(N, F, F(N)).
test_maximum() ->
10 = tail:maximum(10, fun (X) -> X end),
0 = tail:maximum(10, fun (X) -> - X end),
ok.
%% @doc Tail recursive version of fib function
%%
%% fib_aux accumulates value in Current variable
fib_aux(1, _, Value) ->
Value;
fib_aux(N, Previous, Current) when N > 1 ->
fib_aux(N - 1, Current, Previous + Current).
fib(N) ->
fib_aux(N, 0, 1).
test_fib() ->
1 = tail:fib(2),
3 = tail:fib(4),
8 = tail:fib(6),
987 = tail:fib(16),
1100087778366101931 = tail:fib(88), % direct version of fib function would hang here
ok.
%% @doc Step-by-step evaluation of fib(4)
%% fib(4)
%% = fib_aux(4, 0, 1)
%% = fib_aux(3, 1, 1)
%% = fib_aux(2, 1, 2)
%% = fib_aux(1, 2, 3)
%% = 3
%% @doc Convert integer to boolean
to_bool(0) ->
true;
to_bool(_) ->
false.
%% @doc Conditional add
add(true, Number, Sum) ->
Sum + Number;
add(false, _, Sum) ->
Sum.
%% @doc Check if Number is perfect
perfect_aux(Number, Divisor, Sum) when Divisor > 0 ->
Rem = Number rem Divisor, % if Rem == 0 then we have a divisor
CurrentSum = add(to_bool(Rem), Divisor, Sum),
perfect_aux(Number, Divisor - 1, CurrentSum);
perfect_aux(Number, 0, Sum) ->
Number == Sum.
perfect(N) ->
perfect_aux(N, N - 1, 0).
test_perfect() ->
true = tail:perfect(6),
false = tail:perfect(10),
true = tail:perfect(28),
false = tail:perfect(100),
true = tail:perfect(496),
true = tail:perfect(8128),
ok.
test() ->
ok = test_sum(),
ok = test_maximum(),
ok = test_fib(),
ok = test_perfect(),
ok.
@elbrujohalcon
Copy link

Great job!
A few more idiomatic/stylistic comments:

  1. Auxiliary functions, when available, tend to be called just like the main function (i.e. perfect_aux/3 -> perfect/3). The distinction is clear, due to the different arities.
  2. In the same way we generally use snake_case for atoms, we generally use PascalCase for variables (i.e. Current_sum -> CurrentSum)

@mareknowak
Copy link
Author

Thanks.

  1. Auxiliary functions, when available, tend to be called just like the main function (i.e. perfect_aux/3 -> perfect/3). The distinction is clear, due to the different arities.

I know a bit of OCaml and here it gets in the way. In Erlang perfect/3 and perfect/2 are different functions. In OCaml the latter would be a "curried" version of the former and that's why another (auxiliary) function is needed.

  1. In the same way we generally use snake_case for atoms, we generally use PascalCase for variables (i.e. Current_sum -> CurrentSum)

OK.

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