Rotating a list to the right (Prolog)

Question

I have an assignment where I need to rotate a list once to the right. I also have a constraint where I can only use one predicate. It seems that shifting to the left is very easy:

([H|T], R) :- append(T, [H], R).

Though, it seems to be harder to rotate right AND keep the constraint. This is my attempt:

rotate([H], H).
rotate([H|T], F) :- rotate(T,F1), append(F1,T,F).

In my head, it works perfectly, though I only get false as an output. Any help solving this would be much appreciated!

Answer 1

If you have already a predicate, say rotl(L, Rotated) that rotates one to the left, you can use that very same predicate to rotate to the right. Simply put the list into the second argument and keep the first a variable!

That is the deep idea of relations: You can use them in more than one manner!

So to summarize:

rotleft([E|T], R) :-
   append(T,[E],R).

rotright(L, R) :-
   rotleft(R, L).

And here is the most general query that shows you all answers that contain all possible solutions:

| ?- rotright(L,R).
L = [_A],
R = [_A] ? ;
L = [_A,_B],
R = [_B,_A] ? ;
L = [_A,_B,_C],
R = [_C,_A,_B] ? ;
L = [_A,_B,_C,_D],
R = [_D,_A,_B,_C] ? ;
L = [_A,_B,_C,_D,_E],
R = [_E,_A,_B,_C,_D] ? ;
L = [_A,_B,_C,_D,_E,_F],
R = [_F,_A,_B,_C,_D,_E] ? ;
L = [_A,_B,_C,_D,_E,_F,_G],
R = [_G,_A,_B,_C,_D,_E,_F] ? ;
L = [_A,_B,_C,_D,_E,_F,_G,_H],
R = [_H,_A,_B,_C,_D,_E,_F,_G] ? 

Do you see the pattern? For each length of a list (except for the empty list), there is one answer that contains all possible solutions. Look how in one answer the variables are the same. I will take one answer to illustrate this:

L = [_A,_B,_C,_D,_E,_F,_G],
      \  \  \  \  \  \  \____
  ___  \  \  \  \  \  \
     \  \  \  \  \  \  \
R = [_G,_A,_B,_C,_D,_E,_F] ? ;

And here is the most interesting question:

How do lists look like that are the same as the list rotated to the left/right?

Try to formulate that query and look at the answers in detail.

Answer 2

It's important to note that append/3 is rather flexible.

Left rotations are, as you found, easy. You want to get from

[a,b,c]

to

[b,c,a]

By observation, doing that just requires getting the first item from the list (the head) and appending that to the remainder of the list (the tail). In prolog, that's easy:

rotate_left( []     , [] ) .        % rotating an empty list yields the empty list
rotate_left( [L|Ls] , Rotated ) :-  % a left rotation of a non-empty list consist of decomposing it into its head and tail, and
  append( Ls , [L] , Rotated )      % - appending the head to the tail.
  .

A right rotation isn't much more difficult. Again, by observation, you want to get from

[a,b,c]

to

[c,a,b]

You need to get the last item from the list and prepend it to the remainder of the list. Again, you don't need anything more than you did for a left rotation:

rotate_right( []     , []      ) .         % rotating an empty list yields the empty list.
rotate_right( [L|Ls] , Rotated ) :-        % a right rotation of a non-empty list consists of
  append( LeftPrefix , [Last] , [L|Ls] ) , % - deconstructing it into the last item and everything to its left
  Rotated = [Last|LeftPrefix]              % - reconstructing it with the righmost item first
  .

append/3 is very powerful since it can decompose a list into all possible prefixes and suffixes. Feed [a,b,c] into its 3rd argument:

append( Prefix , Suffix , [a,b,c] ).

and, with backtracking, you get the full set of possible ways to create the list [a,b,c]:

Prefix = []      Suffix = [a,b,c]
Prefix = [a]     Suffix = [b,c]
Prefix = [a,b]   Suffix = [c]
Prefix = [a,b,c] Suffix = []