2つのリストをPrologで順序付けしました

Question

L1 = [1,3,5]とL2 = [1,2,4]という2つのリストがある場合、ソート順にそれらをマージするコードを書く必要があります。 cut operatorまたはfailを使用してL3 = [1,1,2,3,4,5] w/oになります。私はPrologとこの問題にどのように接近するのかわからないImに慣れています。誰も私にこれを解決する方法を教えてもらえますか？私は、次のように起動しましたが、しばらくの間、捕まってしまった：

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

Answer 1

これを行うための従来の方法は、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への呼び出しがあるので、あなたが本当に任意の時点でカットをする必要はありません。

Answer 2

宣言的に考えると、ソートされている2つの追加リストからなるマージです。これを2つのサブタスクに分割することができます.1つはリストを追加し、もう1つは結果リストをソートします。あなたが直接プロローグにこのアイデアを置くことができ、ライブラリからの述語の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] 

Answer 3

あなただけの再帰呼び出しでこれを行うにしたい場合は、試すことができます私はそれをもっと効率的に行うことがおそらく可能であると考えています。最初の再帰句は、リストXの先頭がリストYの先頭よりも大きい場合に何をするかを指定します.2番目の再帰句はリスト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).