CODEWITHSUNDEEP
prolog
dopatraman
dopatraman

Reputation: 13908

Swap first two elements of a list in Prolog

I'm doing this exercise from Learn Prolog Now:

Exercise  4.4
Write a predicate swap12(List1,List2) which checks whether List1 is identical to List2 , except that the first two elements are exchanged.

This is what I have so far:

swap12([],[]).
swap12([a, b | Ta], [b, a | Tb]) :- swap12(Ta, Tb).

But when I try to evaluate this I get the following:

?- swap12(X, Y).
X = Y, Y = [] ;
X = [a, b],
Y = [b, a] ;
X = [a, b, a, b],
Y = [b, a, b, a] .

What am I doing wrong?

The goal is to have something like the following:

swap12(X,Y).
X = [a, b].
Y = [b, a].
X = [a, b, b].
Y = [b, a, a].

etc. Please help!

Upvotes: 1

Views: 3881

Answers (1)

lurker
lurker

Reputation: 58234

The first clause:

swap12([],[]).

Says that swapping the first two elements of the empty list is the empty list. I suppose, perhaps, by definition one might say that. But since the empty list has no elements, it may not really be considered to be true.

Your second clause is:

swap12([a, b | Ta], [b, a | Tb]) :- swap12(Ta, Tb).

This says that if you swap the first two elements of [a, b | Ta] the result is [b, a | Tb] if Tb is Ta with its first two elements swapped. This is a rule for any list that starts with a and b, but won't work if you have any other first two elements because a and b are atoms, not variables. Thus, for example, swap12([1,2,3,4], L) would fail since your list starts with 1 and 2, not a and b. In addition, your problem is to swap ONLY the first two elements, whereas your solution has the recursive call to swap12(Ta, Tb) which continues to swap recursively.

Here's what your code really does (it doesn't do what you show in your question, which means the results you show is for a different version of the code you wrote).

?- swap12([a,b], R).
R = [b,a].

?- swap12([b,a], R).
false.    % This fails because `b`, `a` doesn't match `a`, `b`.

?- swap12([a,b,c], R).
false.    % This fails because [a,b,c] has an odd number of elements

?- swap12([a,b,c,d], R).
false.    % This fails because `c`, `d` doesn't match `a` and `b`

?- swap12([a,b,a,b], R).
R = [b, a, b, a].

?- swap12(X, Y).
X = Y, Y = [] ;
X = [a, b],
Y = [b, a] ;
X = [a, b, a, b],
Y = [b, a, b, a] ;
X = [a, b, a, b, a, b],
Y = [b, a, b, a, b, a] ;
X = [a, b, a, b, a, b, a, b],
Y = [b, a, b, a, b, a, b, a] ;
...

The last execution shows you what your rules really mean. It succeeds only if the first list is empty, or any number of a, b pairs and the second list is the same with each a, b pair swapped to b, a.

Let's start over. The problem, again, is to create a rule that is true if the second list is the first list with ONLY the first two elements swapped. A list that has at least two elements looks like [X, Y|T] (the first two elements are X and Y - variables). If I want to swap ONLY the first two elements, I would write, [Y, X|T] so I have swapped X and Y, but keep the same tail, T (I do not want to swap any more elements).

Thus, the rule simply looks like:

swap12([X, Y|T], [Y, X|T]).

This says that if I have a list [X, Y|T], then [Y, X|T] is the same list but with just the first two elements swapped. You can try it out:

?- swap12([a], R).
false.       % fails because `[a]` only has one element!

?- swap12([a,b], R).
R = [b, a].

?- swap12([a,b,c], R).
R = [b, a, c].

?- swap12([a,b,c,d], R).
R = [b, a, c, d].

?- swap12([a,b,c,e,f], R).
R = [b, a, c, e, f].

?- ...

Upvotes: 1

Related Questions