How do I change position of two elements in a list(PROLOG)

Question

predicate change_pos(E1, E2,Lin,Lout).

The Lin has any number of elements, and I need to change all occurences of E1 to E2, and vice-versa. And return in Lout.

I was thinking to do something like this:

change(X, Y, [], []).
change(X, Y, [X|L], [Y,L1]):- change(X,Y,L,L1).
change(X, Y, [Z|L], [Z,L1]:- X \== Z, change(X,Y,L,L1).

But this way is not swiping two number of the list

And you're not changing the position of two elements. You're replacing elements. Two different things. — Enigmativity, Jun 13 '17 at 01:07
You should try something and then show us, rather than just asking us to do the work for you. — Daniel Lyons, Jun 13 '17 at 01:10
I was thinking to do something like this: change(X, Y, [], []). change(X, Y, [X|L], [Y,L1]):- change(X,Y,L,L1). change(X, Y, [Z|L], [Z,L1]:- X \== Z, change(X,Y,L,L1). But this way is not swiping two number of the list — Jessica Simoes, Jun 13 '17 at 01:24
@JessicaSimoes- I think Daniel was letting you know how to ask your question. I don't think he was suggesting he would answer it for you. — Enigmativity, Jun 13 '17 at 02:04
@Enigmativity, I understand, I mean if he could give me a light, could you? — Jessica Simoes, Jun 13 '17 at 02:15
@JessicaSimoes - Try changing `[Y,L1]` to `[Y|L1]` & `[Z,L1]` to `[Z|L1]`. — Enigmativity, Jun 13 '17 at 02:55
You're really close! You're also missing a `)` before the `:-` on the third clause. — Daniel Lyons, Jun 13 '17 at 04:30
@false - I voted to close on the OP's original post. Take a look at that revision. — Enigmativity, Jun 13 '17 at 13:29
@Enigmativity Oh I see. You copied the OP's comment code into the question. I usually try to get them to do it. :) But then, given that code, I don't think there was a basis for closure. — lurker, Jun 13 '17 at 14:59

lurker · Answer 1 · 2017-06-13T18:40:02.173

4

I'm supposing, since this is homework, it's an exercise to learn list processing and recursion. But in Prolog, a common tool for processing each term in turn in a list is maplist:

% Rule for changing one element
change_element(X, Y, X, Y).
change_element(X, Y, Y, X).
change_element(X, Y, Z, Z) :- dif(X, Z), dif(Y, Z).

% Rule for changing a list
change(X, Y, L1, L2) :-
    maplist(change_element(X, Y), L1, L2).

Which yields:

?- change(a, b, [a,b,c,b,a], L).

L = [b, a, c, a, b] ? ;

no
?-

For a determinate solution, you can use if_/3:

change1(X, Y, A, B) :-
    if_(=(Y, A), B = X, A = B).
change2(X, Y, A, B) :-
    if_(=(X, A), B = Y, change1(X, Y, A, B)).

change(X, Y, L1, L2) :- maplist(change2(X, Y), L1, L2).

Which yields:

?- change(a, b, [a,b,c,b,a], L).

L = [b, a, c, a, b].

?-

edited Jun 13 '17 at 18:40

answered Jun 13 '17 at 10:56

lurker

56,987
9
69
103

1

Can you make this determinate? – false Jun 13 '17 at 13:44
... ideally in a separate answer which has been prevented by this closing – false Jun 13 '17 at 14:35
Now you can make another answer! (BTW, = can be used as an operator and `change1/4` is not needed as a separate predicate – false Jun 14 '17 at 09:12

tas · Accepted Answer · 2017-06-13T06:05:41.490

2

You're almost there. Your base case (the empty lists) and your second rule (swap X for Y) are basically fine (apart from the details pointed out in the comments). However, you are missing a rule for vice-versa (swap Y for X). And in your last rule you likely want to make sure that Z differs not only from X but also from Y, otherwise Z would be subject to rule two or three.

change(X, Y, [], []).
change(X, Y, [X|L], [Y|L1]) :-
   change(X,Y,L,L1).
change(X, Y, [Y|L], [X|L1]) :-   % <- vice versa case
   change(X,Y,L,L1).
change(X, Y, [Z|L], [Z|L1]) :-
      dif(X,Z),                  % <- neither X=Z
      dif(Y,Z),                  % <- nor vice versa
      change(X,Y,L,L1).

Here are some example queries. What does [1,2,3,4] look like after swapping 1 with 2 and vice versa?

   ?- change(1,2,[1,2,3,4],L).
L = [2,1,3,4] ? ;
no

What did [2,1,3,4] look like before swapping 1 with 2 and vice versa?

   ?- change(1,2,L,[2,1,3,4]).
L = [1,2,3,4] ? ;
no

Which elements have been swapped in [1,2,3,4] if the resulting list is [2,1,3,4] ?

   ?- change(X,Y,[1,2,3,4],[2,1,3,4]).
X = 1,
Y = 2 ? ;
X = 2,
Y = 1 ? ;
no

edited Jun 13 '17 at 06:05

answered Jun 13 '17 at 05:37

tas

8,100
3
14
22

All this `; no` ... And what about `change(a,a,[a],[a])`'s two (2) redundant answers? – false Jun 13 '17 at 09:09
@false: Fun fact: In Yap the query `?- change(a,a,[a],[a]).` succeeds deterministically. :-) – tas Jun 13 '17 at 15:44
1

In the same way as `repeat.`? Yes? – false Jun 13 '17 at 15:45
@false: Yes. Interesting, I didn't notice that yet. If I'm reading 8.15.3.1 correctly `repeat/0` should not terminate but produce `true` as long as the user hits `;`, right? – tas Jun 13 '17 at 15:59
1

Indeed. That's a 1970s feature of old toplevels: if there is no variable substitution, simply stop. – false Jun 13 '17 at 16:14
@false: That link ... :-D – tas Jun 13 '17 at 16:43

How do I change position of two elements in a list(PROLOG)

2 Answers2