Prolog: Rotate list n times right

Question

Working on a predicate, rotate(L,M,N), where L is a new list formed by rotating M to the right N times.

My approach was to just append the tail of M to its head N times.

rotate(L, M, N) :- 
   (  N > 0,
      rotate2(L, M, N)
   ;  L = M
   ).

rotate2(L, [H|T], Ct) :- 
   append(T, [H], L), 
   Ct2 is Ct - 1, 
   rotate2(L, T, Ct2).

Currently, my code returns L equal to the original M, no matter what N is set to. Seems like when I'm recursing, the tail isn't properly moved to the head.

Hint: you can do this much more efficiently with just two calls to `append`. — Fred Foo, May 08 '13 at 00:30
@larsmans Do you mean only two calls to append? Do I need to be continually decreasing N? — Adam Duvall, May 08 '13 at 00:47

score 9 · Accepted Answer · 2013-05-09T01:00:36.163

9

You can use append to split lists, and length to create lists:

% rotate(+List, +N, -RotatedList)
% True when RotatedList is List rotated N positions to the right
rotate(List, N, RotatedList) :-
    length(Back, N),           % create a list of variables of length N
    append(Front, Back, List), % split L
    append(Back, Front, RotatedList).

Note: this only works for N <= length(L). You can use arithmetic to fix that.

Edit for clarity This predicate is defined for List and N arguments that are not variables when the predicate is called. I inadvertently reordered the arguments from your original question, because in Prolog, the convention is that strictly input arguments should come before output arguments. So, List and N and input arguments, RotatedList is an output argument. So these are correct queries:

?- rotate([a,b,c], 2, R).
?- rotate([a,b,c], 1, [c,a,b]).

but this:

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

will go into infinite recursion after finding one answer.

When reading the SWI-Prolog documentation, look out for predicate arguments marked with a "?", as in length. They can be used as shown in this example.

edited May 09 '13 at 01:00

answered May 08 '13 at 01:50

I'm not seeing how to make this work for `N > length(L)`. Seems like it would need some kind of recursive call to rotate while changing/tracking the value of N. But that seems like over complicating things. – Adam Duvall May 08 '13 at 21:56
@AdamDuvall Modular arithmetic – May 08 '13 at 23:11
So, currently it times out if `N > length(L)`, is the idea that there is some way to use mod so that it stops at some point and doesn't time out? – Adam Duvall May 08 '13 at 23:46
I get that rotating it `length(L) + 1` times is the same as rotating it once. I just don't get the translation of that into prolog syntax. By timing out, I mean `?- rotate(L, [1,2,3,4], 5).` results in the program timing out rather than evaluating false, or incorrectly. – Adam Duvall May 09 '13 at 00:40

Prolog: Rotate list n times right

1 Answers1

Linked