Tail of the recursive merge algorithm
I have implemented a recursive merge algorithm:
-module(ms).
-import(lists,[sublist/3,delete/2,min/1,reverse/1]).
-export([mergesort/1]).
mergesort([])->
[];
mergesort([N])->
N;
mergesort(L)->
mergesort(split(1,L),split(2,L),[]).
mergesort(L1,L2,[])->
case {sorted(L1),sorted(L2)} of
{true,true}->
merge(L1,L2,[]);
{true,false}->
merge(L1,mergesort(split(1,L2),split(2,L2),[]),[]);
{false,true}->
merge(mergesort(split(1,L1),split(2,L1),[]),L2,[]);
{false,false}->
merge(mergesort(split(1,L1),split(2,L1),[]),mergesort(split(1,L2),split(2,L2),[]),[])
end.
merge([],[],R)->
reverse(R);
merge(L,[],R)->
merge(delete(min(L),L),[],[min(L)|R]);
merge([],L,R)->
merge([],delete(min(L),L),[min(L)|R]);
merge([H1|T1],[H2|T2],R) when H1 < H2 ->
merge(T1,[H2|T2],[H1|R]);
merge([H1|T1],[H2|T2],R) when H1 >= H2 ->
merge([H1|T1],T2,[H2|R]).
split(1,L)->
sublist(L,1,ceiling(length(L)/2));
split(2,L)->
sublist(L,ceiling(length(L)/2+1),length(L)).
ceiling(X) when X < 0 ->
trunc(X);
ceiling(X) ->
T = trunc(X),
case X - T == 0 of
true -> T;
false -> T + 1
end.
However, I am annoyed by the fact that mergesort/3
it is not tail-recursive (TR) and is verbose.
I guess the problem here is that I don't particularly understand the TR pattern that I will be using here - I understand how to implement a TR function that can be defined in terms of a series, for example - that would just move the arguments into a function up the row, however for the case where we concatenate subnets conditionally with natural recursion of the rest of the list, I don't know.
So I would like to ask:
1) How can I make mergesort/3
TR?
2) What resources can I use to deeply understand Erlang recursion?
source to share
Your merge sort is not tail recursion, because the last function called mergesort / 3 is merge / 3. You are calling mergesort as arguments to the merge, so the stack must grow - the top call to mergesort / 3 has not finished yet, and its stack stack cannot be reused. To write it in a TR approach, you need to think about this as importantly as possible. Each TR function is easily overwritten with an iterative while loop. Consider:
loop(Arg) ->
NewArg = something_happens_to(Arg),
loop(NewArg) or return NewArg.
and
data = something;
while(1){
...
break loop or modify data block
...
} // data equals to NewArg at the end of iteration
Here is my example of TR merge sort. This is an upward mindset. I used the merge / 3 function from your module.
ms(L) ->
ms_iteration([[N] || N <- L], []).
ms_iteration([], []) -> % nothing to do
[];
ms_iteration([], [OneSortedList]) -> % nothing left to do
OneSortedList;
ms_iteration([], MergedLists) ->
ms_iteration(MergedLists, []); % next merging iteration
ms_iteration([L], MergedLists) -> % can't be merged yet but it sorted
ms_iteration([], [L | MergedLists]);
ms_iteration([L1, L2 | ToMergeTail], MergedLists) -> % merging two sorted lists
ms_iteration(ToMergeTail, [merge(L1, L2, []) | MergedLists]).
Well said here: http://learnyousomeerlang.com/recursion .
source to share