diff options
author | Trygve Laugstøl <trygvis@inamo.no> | 2024-02-23 07:08:18 +0100 |
---|---|---|
committer | Trygve Laugstøl <trygvis@inamo.no> | 2024-02-23 07:08:18 +0100 |
commit | 5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e (patch) | |
tree | 982ca2e7f9ac4e8c350dfb5c4f60bcfdfff5afaf /learn-you-some-erlang/recursive.erl | |
parent | 05ae56e5e89abf2993f84e6d52b250131f247c35 (diff) | |
download | erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.tar.gz erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.tar.bz2 erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.tar.xz erlang-workshop-5a9cdd3cc89507d4d74f8bded56ce5e037b3b56e.zip |
wip
Diffstat (limited to 'learn-you-some-erlang/recursive.erl')
-rw-r--r-- | learn-you-some-erlang/recursive.erl | 135 |
1 files changed, 135 insertions, 0 deletions
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. |