2014-11-23 137 views
3

我已經實現了一個遞歸算法歸併:尾遞歸算法歸併

-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. 

但是我的事實,mergesort/3不是尾遞歸(TR)厭煩,並且是冗長。

我想這裏的問題是,我不是特別意識到TR'模板',我會在這裏使用 - 我明白我將如何實現TR功能,可以根據一系列的定義,例如 - 這隻會將參數移到該系列的函數中,但對於我們將一個子列表有條件地合併到列表的其餘部分的自然遞歸的情況,我是無知的。

因此,我想問一下:

1)我怎樣才能讓mergesort/3 TR?

2)我可以使用哪些資源深入理解erlang尾遞歸?

回答

2

您的合併排序不是尾遞歸,因爲在mergesort/3中調用的最後一個函數是merge/3。你調用mergesort作爲合併的參數,所以堆棧必須增長 - upper被稱爲mergesort/3還沒有完成,它的堆棧幀不能被重用。 要用TR方法編寫它,你需要儘可能地將它想象得更加緊湊。每個TR功能都可以輕鬆地重複寫入循環中的迭代。試想一下:

loop(Arg) -> 
    NewArg = something_happens_to(Arg), 
    loop(NewArg) or return NewArg. 

和:

data = something; 
while(1){ 
    ... 
    break loop or modify data block 
    ... 
} // data equals to NewArg at the end of iteration 

這裏是我的TR合併排序的例子。這是自下而上的思維方式。我使用了模塊中的merge/3功能。

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's sorted 
    ms_iteration([], [L | MergedLists]); 
ms_iteration([L1, L2 | ToMergeTail], MergedLists) -> % merging two sorted lists 
    ms_iteration(ToMergeTail, [merge(L1, L2, []) | MergedLists]). 

這裏很好解釋:http://learnyousomeerlang.com/recursion