Last active
May 9, 2020 03:27
-
-
Save mareknowak/22f5dc1b9fa7c665281f1a592633e476 to your computer and use it in GitHub Desktop.
Tail recursion - FP in Erlang 2.5
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% @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. |
Thanks.
- 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.
- 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
Great job!
A few more idiomatic/stylistic comments:
perfect_aux/3
->perfect/3
). The distinction is clear, due to the different arities.Current_sum
->CurrentSum
)