Two ascending lists of numbers X and Y are given.I need to write a predicate p(X,Y,Z), which, as the value of the variable Z, gives a general ordered list of elements X and Y. For example, ?– p([1,3,5,7,8], [2,3,5,7],Z). Z=[1,2,3,3,5,5,7,7,8]
my first attempt:
p([],X,X).
p(Y,[],Y).
p([HLIST1|LIST1],[HLIST2|LIST2],[HLIST1|Z]):- HLIST1 < HLIST2,!,p(LIST1,LIST2,Z).
p([HLIST1|LIST1],[HLIST2|LIST2],[HLIST2|Z]):- HLIST2 =< HLIST1,!,p(LIST1,LIST2,Z).
swi prolog gave me false
second attempt:
p([],X,X).
p(Y,[],Y).
p([HLIST1|LIST1],[HLIST2|LIST2],[HLIST1|Z]):- HLIST1 < HLIST2,!,p(LIST1,[HLIST2|LIST2],Z).
p([HLIST1|LIST1],[HLIST2|LIST2],[HLIST2|Z]):- HLIST2 =< HLIST1,!,p([HLIST1|LIST1],LIST2,Z).
this version works correctly
I searched the internet and found that a recursive call is made with a head and tail split of one of the lists.
p([HLIST1|LIST1],[HLIST2|LIST2],[HLIST2|Z]):- HLIST2 =< HLIST1,!,p([HLIST1|LIST1],LIST2,Z).
Can someone explain why this is necessary and what it gives?....after all, with a recursive call, there will be another division of the list, won't there? I am a beginner, so I would be glad for a detailed explanation.
From your program,
p([],X,X).
p(Y,[],Y).
p([HLIST1|LIST1],[HLIST2|LIST2],[HLIST1|Z]):-
HLIST1 < HLIST2, !,
p(LIST1,[HLIST2|LIST2],Z).
p([HLIST1|LIST1],[HLIST2|LIST2],[HLIST2|Z]):-
HLIST2 =< HLIST1, !,
p([HLIST1|LIST1],LIST2,Z).
First clause: if the list in the first argument is empty, then unify the third argument with the list in the second argument.
Second clause: if the list in the second argument is empty, then unify the third argument with the list in the first argument.
Third clause: if the first element of the list in the first argument is less than the first element of the list in the second argument, HLIST1 < HLIST2, then put this element in the list in the third argument [HLIST1|Z], list that will be followed by something else Z. Then, do not consider other possibilities (cut, !) and recursively call the same predicate p/3, p(LIST1,[HLIST2|LIST2],Z) with the remaining of the list in the first argument (the element has been already considered and placed in the list in the third argument), the same list of the second argument, since no elements have been considered from this list, and the remaining of the list in the third argument (Z), that will be filled with the subsequent recursive calls.
Fourth clause: same as before, but considers the case where the first element in the list in the second argument should be placed in the list in the third argument.
Hope this is clear.