How to construct pair of items on two lists using recursion in prolog-CodePudding

Hie, I am a newbie in Prolog, especially recursion in Prolog. Here, start recursive on list X, makepairs recursive on list Y. These two rules should make a list of the pairs of items on X and Y. For example, if I enter query:

?- start([a,b], [c,d], Z)

Prolog should print out:

Z = [pair(a,c), pair(a,d), pair(b,c), pair(b,d)].

But my code prints only false. Could anyone help to find the bug in my code?

start([H|T], Y, Z):- makepairs(H, Y, Z), start(T, Y, Z).
start([], _Y, []).

makepairs(X, [H|T], Z) :- append([pair(X,H)], [], Z), makepairs(X, T, Z).      
makepairs(_X, [], _Z).

CodePudding user response：

Using library(lamdba) preinstalled in Scryer, available for SICStus|SWI.

start(Xs, Ys, XYs) :-
   maplist(\X^Y^pair(X,Y)^true, Xs, Ys, XYs).

Or manually,

list_list_pairs([], [], []).
list_list_pairs([X|Xs], [Y|Ys], [pair(X,Y)|Pairs]) :-
   list_list_pairs(Xs, Ys, Pairs).

Note that this not only constructs such pairs, but it can also be used to "unzip" them:

?- list_list_pairs(Xs, Ys, [pair(1,one), pair(2,two), pair(3,three)]).
   Xs = [1,2,3], Ys = [one,two,three].

But, maybe I should add, using pair/2 as a functor is fairly uncommon. It is more idiomatic in Prolog to use (-)/2 instead, which is so much more compact, think of

   Ps = [1-one,2-two,3-three].
% vs
   Ps = [pair(1,one), pair(2,two), pair(3,three)]

CodePudding user response：

Assuming that this is a learning exercise, you are supposed to roll your own...

For the purposes of this exercise, I'm going to elect to represent the tuple using the :/2 operator (x:y), simply because it's less typing, more compact, and and easier on the eyes than, say, [x,y].

So, there are 3 cases in this problem:

Both lists are the empty list. The result is the empty list. You can represent that as
```
zip( [] , [] , [] ) .
```
Both lists are non-empty lists. The result is that we prepend the pair to the result list, and continue, thus:
```
zip( [X|Xs] , [Y|Ys] , [X:Y|Zs] ) :- zip(Xs,Ys,Zs) .
```
And then, there is the case where one list is empty and the other is non-empty. You need to consider how to handle that situation. You could
- Fail.
- Terminate the program and succeed, discarding the unmatched items.
- Include the unpaired item as itself.
- Include the unpaired item in the same x:y pair structure, selecting some atom to represent the missing data.
Here, I choose to include the last option, and will represent the missing data with the atom nil, so [nil:y] or [x:nil].

You can represent this in Prolog as
```
zip( []     , [Y|Ys] , [nil:Y|Zs] ) :- zip([],Ys,Zs) .
zip( [X|Xs] , []     , [X:nil|Zs] ) :- zip(Xs,[],Zs) .
```

Putting it all together, you get this:

zip( []     , []     , []         ) .
zip( []     , [Y|Ys] , [nil:Y|Zs] ) :- zip([],Ys,Zs) .
zip( [X|Xs] , []     , [X:nil|Zs] ) :- zip(Xs,[],Zs) .
zip( [X|Xs] , [Y|Ys] , [X:Y|Zs]   ) :- zip(Xs,Ys,Zs) .

which you can fiddle with at https://swish.swi-prolog.org/p/zip/unzip.pl

Running

zip( [a,b,c], [1,2,3], Ps ).

results in

P = [ a:1, b:2, c:3 ]

You might note that this will also unzip a list of tuples, so running

zip(Xs,Ys,[a:1,b:2,c:3]).

results in

Xs = [a,b,c]
Ys = [1,2,3]

CodePudding user response：

This line cannot succeed:

start([H|T],Y,Z):- makepairs(H,Y,Z), start(T,Y,Z).

The first part requires Prolog to find a value for Z which is the list of all pairs, the second part requires Z to become only the list of H paired with every element in Y, and the third part requires Z to become the pairs of the tail and Y.

One single Z cannot be three different things at the same time, the predicate cannot hold, and false must be the result.

This line:

start([],_Y,[]).

Introduces a helper variable, which you never use.

This line:

makepairs(X,[H|T],Z):-append([pair(X,H)],[], Z), makepairs(X,T,Z).

requires that Z is the list of pairs of X with everything in [H|T], and also that Z is what you get when you append an empty list onto a list with one pair, and that Z is the list of pairs of X with T. This has the same problem of requiring Z to be three different things. These lines are where you need to introduce helper variables such as Z_.

CodePudding user response：

Flaws in the predicate makepairs/3

In the base case, makepairs(_X, [], _Z), the variable _Z remains free, but it should be instantiated to [].
In the recursive case, append([pair(X, H), [], Z] is equivalent to Z = [pair(X, H)] (however, all you need is Z = pair(X,H)); also, the recursive call must produce a list containing the remaining pairs, say Zs. So the final result should be [Z|Zs].

Thus, a correct code is:

makepairs(_X, [], []).
makepairs(X, [H|T], [Z|Zs]):-
    Z = pair(X,H),
    makepairs(X, T, Zs).

Example:

?- makepairs(a, [c,d], Pairs).
Pairs = [pair(a, c), pair(a, d)] ;
false. % <= spurious choice point!

Flaws in predicate start/3

In the recursive case, subgoal makepairs(H, Y, Z) produces a list Z containing only pairs whose first elements are equal to H; then, the recursive call must produce a list Zs containing the remaining pairs. So, the final result, say Zss, must be the concatenation of lists Z and Zs.

Thus, a correct code is:

start([], _Y, []).
start([H|T], Y, Zss):-
    makepairs(H, Y, Z),
    append(Z, Zs, Zss),
    start(T, Y, Zs).

Example:

?- start([a,b], [c,d], Z).
Z = [pair(a, c), pair(a, d), pair(b, c), pair(b, d)] ;
false. % <= spurious choice point

A BETTER SOLUTION

A better solution, that avoid spurious choice point using first argument indexing, is:

make_pairs([], _, []).
make_pairs([X|Xs], Y, Pairs):-
    make_pairs_helper(Y, X, Px),
    append(Px, Pxs, Pairs),
    make_pairs(Xs, Y, Pxs).

make_pairs_helper([], _, []).
make_pairs_helper([Y|Ys], X, [pair(X,Y)|Zs]):- 
    make_pairs_helper(Ys, X, Zs).

Example:

?- make_pairs([a,b], [c,d], Pairs).
Pairs = [pair(a, c), pair(a, d), pair(b, c), pair(b, d)].

Remark It's more idiomatic to use - as separator of the elements of a pair in Prolog.