2016-03-23 67 views
0

給定兩個列表:L1 = [1,3,5]和L2 = [1,2,4],我需要編寫代碼以排序順序合併它們,所以結果將使用cut operatorfail L3 = [1,1,2,3,4,5] w/o。我熟悉Prolog和我不知道如何解決這個問題。有誰能告訴我如何解決這個問題嗎?我已經開始喜歡以下,但卡住了一段時間:在Prolog中將兩個列表合併到一起訂購

merge([], [], []). 
merge([], L, L). 
merge(L, [], L). 
merge([H1|T1], [H2|T2], [L|Rest]:- 
    H1 =< H2 -> L = merge(H1 
+1

它看起來好像你的問題的一部分缺失......如何編輯你的問題,並添加這些部分? – repeat

回答

2

傳統的方式做,這是使用compare/3。評估時,它將其第一個參數綁定到<=>。然後,您可以使用此值作爲輔助謂詞的第一個參數:

... 
compare(Order, X, Y), 
merge_aux(Order, X, Y, Xs, Ys, Merged). 

merge_aux(<, X, Y, ... 
merge_aux(=, X, Y, ... 
merge_aux(>, X, Y, ... 

的調用compare/3是確定性的,因此是調用merge_aux,所以你並不需要在任何時候削減。

+0

但是'compare/3'就像'(@<)/ 2'等一樣,而不是像評估參數的'(= <)/ 2'。 – false

+0

@false是的。 OP沒有指定列表是嚴格整數,數字,算術表達式還是基礎條件,或者任何術語,可能是變量。 '比較/ 3'僅適用於算術表達式,有理數或變量。 –

+0

OP有意或無意地給出了(= <)/ 2 :-)。但'(= <)/ 2'的好處在於它會爲所有討厭的情況產生一個實例化錯誤。 – false

0

如果您以聲明方式思考它,您想要描述的是由兩個附加列表組成的合併,這兩個列表經過排序。您可以將其分成2個子任務:一個附加列表和另一個排序結果列表。使用謂詞append/3可以從庫(列表)和內置謂詞msort你可以直接把/ 2下這個想法在序言:

:- use_module(library(lists)). 

merge(L1,L2,L3) :- 
    append(L1,L2,X), 
    msort(X,L3). 

?- merge([1,3,5],[1,2,4],L). 
L = [1,1,2,3,4,5] 
0

如果你想這樣做,只是遞歸調用,您可以嘗試下面,我認爲它可能更有效地做到這一點。第一個遞歸子句指定如果List X的頭部大於List Y的頭部,則第二個遞歸子句反之亦然。這將處理不同長度的列表。

我正在合併排序,所以現在需要解決其餘的問題。下一步如何將列表排列一半!

merge_ordered_lists([], [], []). 
merge_ordered_lists(Xs, [], Xs). 
merge_ordered_lists([], Ys, Ys). 
merge_ordered_lists([X|Xs], [Y|Ys], [X|Rs]) :- 
    X =< Y, 
    merge_ordered_lists(Xs, [Y|Ys], Rs). 
merge_ordered_lists([X|Xs],[Y|Ys], [Y|Rs]) :- 
    X > Y, 
    merge_ordered_lists([X|Xs], Ys, Rs). 
+1

'? - merge_ordered_lists([],[],[])。'成功三次! – false