İki listeyi bir araya getirme Prolog

Question

İki liste verildiğinde: L1 = [1,3,5] ve L2 = [1,2,4], bunları sıralanmış sırayla birleştirmek için kod yazmam gerekiyor, sonuç cut operator veya fail kullanılarak L3 = [1,1,2,3,4,5] olacaktır. Prolog'la aşina oldum ve bu probleme nasıl yaklaşacağımı bilmiyorum. Lütfen bunu nasıl çözeceğimi söyler misiniz? Aşağıdaki gibi başlayan ettik ama bir süre saplanıp:

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

Answer 1

Bunu yapmanın geleneksel yolu compare/3 kullanmaktır. Değerlendirildiğinde, ilk bağımsız değişkenini <, = veya > olarak bağlar. compare/3 için

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

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

çağrı deterministik olduğunu ve bu yüzden merge_aux çağrısı, bu nedenle gerçekten herhangi bir noktada keser gerekmez: Bu durumda, bir yardımcı yüklemi ilk argüman olarak bu değeri kullanabilirsiniz.

Answer 2

Beyannameyle ilgili olarak düşünürseniz, tanımlamak istediğiniz şey, sıralanan iki ek listeden oluşan bir birleştirme işlemidir. Bunu 2 alt araca bölebilirsiniz: Biri listelere ekleme ve bir diğeri ortaya çıkan listeyi sıralama. yüklem kitaplığı (listelerinden) dan/3 eklemek kullanma ve yerleşik yüklem/2 doğrudan önbölüküne bu fikri indirdi msort: sadece deneyebileceğiniz özyinelemeli çağrılar ile bunu istiyorsanız

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

Aşağıda, muhtemelen daha verimli bir şekilde yapılabileceğini düşünüyorum. İlk özyinelemeli yan tümce, Liste X'in başı, Liste Y'nin başlığından daha büyükse, ikinci özyineleme koşulu tersi ne yapılacağını belirtir. Bu farklı uzunlukların listeleri ile ilgilenecektir.

Şimdi birleştirme sıralama üzerinde çalışıyorum, bu yüzden artık diğerlerini çalıştırmanız gerekiyor. Bir sonraki adım bir listeyi yarıya nasıl kesilir!

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