From 5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e Mon Sep 17 00:00:00 2001
From: Trygve Laugstøl <trygvis@inamo.no>
Date: Fri, 23 Feb 2024 07:08:18 +0100
Subject: wip

---
 learn-you-some-erlang/recursive.erl | 135 ++++++++++++++++++++++++++++++++++++
 1 file changed, 135 insertions(+)
 create mode 100644 learn-you-some-erlang/recursive.erl

(limited to 'learn-you-some-erlang/recursive.erl')

diff --git a/learn-you-some-erlang/recursive.erl b/learn-you-some-erlang/recursive.erl
new file mode 100644
index 0000000..96a046c
--- /dev/null
+++ b/learn-you-some-erlang/recursive.erl
@@ -0,0 +1,135 @@
+-module(recursive).
+-export([fac/1, tail_fac/1, len/1, tail_len/1, duplicate/2,
+         tail_duplicate/2, reverse/1, tail_reverse/1, sublist/2, 
+         tail_sublist/2, zip/2, lenient_zip/2, tail_zip/2,
+         tail_lenient_zip/2]).
+-export([quicksort/1, lc_quicksort/1, bestest_qsort/1]).
+
+%% basic recursive factorial function
+fac(0) -> 1;
+fac(N) when N > 0 -> N*fac(N-1).
+
+%% tail recursive version of fac/1
+tail_fac(N) -> tail_fac(N,1).
+
+tail_fac(0,Acc) -> Acc;
+tail_fac(N,Acc) when N > 0 -> tail_fac(N-1,N*Acc).
+
+%% finds the len of a list
+len([]) -> 0;
+len([_|T]) -> 1 + len(T).
+
+%% tail recursive version of len/1
+tail_len(L) -> tail_len(L,0).
+
+tail_len([], Acc) -> Acc;
+tail_len([_|T], Acc) -> tail_len(T,Acc+1).
+
+%% duplicates Term N times
+duplicate(0,_) ->
+    [];
+duplicate(N,Term) when N > 0 ->
+    [Term|duplicate(N-1,Term)].
+
+%% tail recursive version of duplicate/2
+tail_duplicate(N,Term) ->
+    tail_duplicate(N,Term,[]).
+
+tail_duplicate(0,_,List) ->
+    List;
+tail_duplicate(N,Term,List) when N > 0 ->
+    tail_duplicate(N-1, Term, [Term|List]).
+
+%% reverses a list (a truly descriptive function name!)
+reverse([]) -> [];
+reverse([H|T]) -> reverse(T)++[H].
+
+
+%% tail recursive version of reverse/1
+tail_reverse(L) -> tail_reverse(L,[]).
+
+tail_reverse([],Acc) -> Acc;
+tail_reverse([H|T],Acc) -> tail_reverse(T, [H|Acc]).
+
+
+%% returns the N first elements of a list
+sublist(_,0) -> [];
+sublist([],_) -> [];
+sublist([H|T],N) when N > 0 -> [H|sublist(T,N-1)].
+
+%% tail recursive version of sublist/2
+tail_sublist(L, N) -> reverse(tail_sublist(L, N, [])).
+
+tail_sublist(_, 0, SubList) -> SubList;
+tail_sublist([], _, SubList) -> SubList;
+tail_sublist([H|T], N, SubList) when N > 0 ->
+    tail_sublist(T, N-1, [H|SubList]).
+
+%% Takes two lists [A] and [B] and returns a list of tuples
+%% with the form [{A,B}]. Both lists need to be of same lenght.
+zip([],[]) -> [];
+zip([X|Xs],[Y|Ys]) -> [{X,Y}|zip(Xs,Ys)].
+
+%% Same as zip/2, but lists can vary in lenght
+lenient_zip([],_) -> [];
+lenient_zip(_,[]) -> [];
+lenient_zip([X|Xs],[Y|Ys]) -> [{X,Y}|lenient_zip(Xs,Ys)].
+
+%% tail recursive version of zip/2
+tail_zip(X,Y) -> reverse(tail_zip(X,Y,[])).
+
+tail_zip([],[],Acc) -> Acc;
+tail_zip([X|Xs],[Y|Ys], Acc) ->
+    tail_zip(Xs,Ys, [{X,Y}|Acc]).
+
+%% tail recursive version of lenient-zip/2
+tail_lenient_zip(X,Y) -> reverse(tail_lenient_zip(X,Y,[])).
+
+tail_lenient_zip([],_,Acc) -> Acc;
+tail_lenient_zip(_,[],Acc) -> Acc;
+tail_lenient_zip([X|Xs],[Y|Ys], Acc) ->
+    tail_lenient_zip(Xs,Ys,[{X,Y}|Acc]).
+
+%% basic quicksort function.
+quicksort([]) -> [];
+quicksort([Pivot|Rest]) ->
+    {Smaller, Larger} = partition(Pivot,Rest,[],[]),
+    quicksort(Smaller) ++ [Pivot] ++ quicksort(Larger).
+
+partition(_,[], Smaller, Larger) -> {Smaller, Larger};
+partition(Pivot, [H|T], Smaller, Larger) ->
+    if H =< Pivot -> partition(Pivot, T, [H|Smaller], Larger);
+       H >  Pivot -> partition(Pivot, T, Smaller, [H|Larger])
+    end. 
+
+%% quicksort built with list comprehensions rather than with a
+%% partition function.
+lc_quicksort([]) -> [];
+lc_quicksort([Pivot|Rest]) ->
+    lc_quicksort([Smaller || Smaller <- Rest, Smaller =< Pivot])
+    ++ [Pivot] ++
+    lc_quicksort([Larger || Larger <- Rest, Larger > Pivot]).
+
+%% BESTEST QUICKSORT, YEAH!
+%% (This is not really the bestest quicksort, because we do not do
+%%  adequate pivot selection. It is the bestest of this book, alright?
+%%  Thanks to literateprograms.org for this example. Give them a visit!
+%%  http://en.literateprograms.org/Quicksort_(Erlang) )
+bestest_qsort([]) -> [];
+bestest_qsort(L=[_|_]) ->
+    bestest_qsort(L, []).
+
+bestest_qsort([], Acc) -> Acc;
+bestest_qsort([Pivot|Rest], Acc) ->
+    bestest_partition(Pivot, Rest, {[], [Pivot], []}, Acc).
+
+bestest_partition(_, [], {Smaller, Equal, Larger}, Acc) ->
+    bestest_qsort(Smaller, Equal ++ bestest_qsort(Larger, Acc));
+bestest_partition(Pivot, [H|T], {Smaller, Equal, Larger}, Acc) ->
+    if H < Pivot ->
+           bestest_partition(Pivot, T, {[H|Smaller], Equal, Larger}, Acc);
+       H > Pivot ->
+           bestest_partition(Pivot, T, {Smaller, Equal, [H|Larger]}, Acc);
+       H == Pivot ->
+           bestest_partition(Pivot, T, {Smaller, [H|Equal], Larger}, Acc)
+    end.
-- 
cgit v1.2.3