CODEWITHSUNDEEP
prolog
Mark
Mark

Reputation: 11

Merging two lists into on ordered in Prolog

Given two lists: L1 = [1,3,5] and L2 = [1,2,4], I need to write code to merge them in sorted order, so the result would be L3 = [1,1,2,3,4,5] w/o using cut operator or fail. I'm getting familiar with Prolog and Im not sure how to approach this problem. Could anybody please tell me how to solve this? I've starting like the following but got stuck for awhile:

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

Upvotes: 0

Views: 1895

Answers (3)

user7910795
user7910795

Reputation:

If you want to do this just with recursive calls you can try the below, I figure it is probably possible to do it more efficiently. The first recursive clause specifies what to do if the head of List X is greater than the head of List Y, the second recursive clause vice-versa. This will deal with lists of different lengths.

I am working on a merge sort so now need to work out the rest. Next step how to chop a list in half!

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

Upvotes: 0

tas
tas

Reputation: 8140

If you think about it declaratively, what you want to describe is a merge that consists of two appended lists that are sorted. You can divide this into 2 subtasks: One appending the lists and another sorting the resulting list. Using the predicate append/3 from library(lists) and the built-in predicate msort/2 you can directly put down this idea in prolog:

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

Upvotes: 0

user1812457
user1812457

Reputation:

The traditional way to do this is to use compare/3. When evaluated, it binds its first argument to <, =, or >. You can then use this value as the first argument of an auxiliary predicate:

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

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

The call to compare/3 is deterministic, and so is the call to merge_aux, so you don't really need cuts at any point.

Upvotes: 2

Related Questions