1

i am working on merging of lists in PROLOG. What are the possible changes i need to do to make my code show these outputs.

?- merge(X, [1,2], [1,2,3]).  # lists that merge with [1,2] to give [1,2,3]
X = [1,2,3] ? ;
X = [1,3] ? ;
X = [2,3] ? ;
X = [3] ? ;
no

?- merge(X, Y, [1,2]).        # pairs of lists that merge to give [1,2]
X = [], Y = [1,2] ? ;
X = [1,2], Y = [] ? ;
X = [1], Y = [1,2] ? ;
X = [1,2], Y = [1] ? ;
X = [1,2], Y = [1,2] ?
X = [1], Y = [2] ? ;
X = [1,2], Y = [2] ? ;
X = [2], Y = [1] ? ;
X = [2], Y = [1,2] ? ;
no

The code i am using for merge right now is

merge( [], RS, RS ).
merge( LS, [], LS ).
merge( [L|LS], [R|RS], [L|T] ) :- L =< R, merge(    LS, [R|RS], T).
merge( [L|LS], [R|RS], [R|T] ) :- L > R,  merge( [L|LS],   RS,  T).

Thanks in advance

Muhammad Azib Ali
  • 11
  • 2
  • Where did the `merge` predicate you are showing come from? What have you tried so far to solve your problem and what specific question do you have? – lurker May 29 '18 at 10:20
  • merge is the one which we usually design for mergesort. and i am trying to make it as if when i don't give two lists for merging and only the merged list. it shows me the combination of lists which can be the possible combination for that list – Muhammad Azib Ali May 29 '18 at 12:13
  • That's what `merge` is and does, but it didn't tell me where it came from. And you didn't answer my other question. – lurker May 29 '18 at 12:54
  • 1
    Your definition fails for `merge([1,2,3], [1,2], [1,2,3]).` It seems that *certain* duplicates get suppressed. – false May 29 '18 at 18:56
  • Your examples give the impression that you are interested in set union. If so, you might find [this post](https://stackoverflow.com/a/27358600/6101159) interesting. – tas May 29 '18 at 20:58

1 Answers1

0

Move the comparison (=</>) after the recursive call:

merge( [], RS, RS ).
merge( LS, [], LS ).
merge( [L|LS], [R|RS], [L|T] ) :- merge(    LS, [R|RS], T), L =< R.
merge( [L|LS], [R|RS], [R|T] ) :- merge( [L|LS],   RS,  T), L > R.

=</> do not work with unbound variables, but if you move the comparison after the call to merge, the variables L and R will be bound to some value by the recursive call.

?- merge([1,2,3],[2,4,6],X).
X = [1, 2, 2, 3, 4, 6] ;
false.

?- merge([1,2,3],X,[1,2,3,4]).
X = [4] ;
false.

?- merge(Y,X,[1,2,3,4]).
Y = [],
X = [1, 2, 3, 4] ;
Y = [1, 2, 3, 4],
X = [] ;
Y = [1],
X = [2, 3, 4] ;
Y = [1, 2],
X = [3, 4] ;
...
fferri
  • 18,285
  • 5
  • 46
  • 95