🚀 go-pugleaf

In article <578@tower1.uucp>, arjen@disnet.uucp (Arjen Duursma) writes:
> I would not recommend the use of length

Using length/2 has an important benefit:  it enables the rotate/3
predicate to _solve_ for the Shift.  It is always a Good Thing if we
can write code that has no restrictions having no apparent motivation
in the _meaning_ of the operation.

> To avoid append, use difference lists.

Please, people, do *NOT* use L1-L2 data structures.  Don't even
_say_ "difference lists".  Say "list differences" or better still
"difference pairs".  Use two arguments.  You will save a lot of space
at run-time.

> Fast attempt (definately not tested):
> 
> rotate(List,Shift,RotatedList) :-
> 	Shift < 0,!,NewShift is -Shift,
> 	rotate(RotatedList,NewShift,List).
> rotate(List,Shift,RotatedList) :-
> 	rot(Shift,List,RotatedList,L-L).
> 
> rot(0,L1,L2,L2-L1) :- !. /* this is the append */
> rot(X,[H|T],RotatedList,Dh-[H|Dt]) :-
> 	NewX is X - 1,
> 	rot(NewX,T,RotatedList,Dh-Dt).

Recall the picture:

	OriginalList	    RotatedList
	+-----+-----+       +-----+-----+
	|  A  |  Z  |  ==>  |  Z  |  A  |
	+-----+-----+       +-----+-----+
	|<-N->|                   |<-N->|

Let the length of the original list be L >= N.  It is evident that
in constructing the rotated list we may have to allocate L new cons
cells.  It is also evident that the rot/4 predicate above will only
allocate N new cons cells.  Therefore that definition cannot be right.
In fact I find that
	L = [a,b,c,d], rotate(L, N, R)
yields R = L for N = 0..4.  Not quite what was wanted.  It usually is
a good idea to test code before posting.

So, let's look in the Quintus library to see what might get us a bit
closer.  There is a predicate

%   append_length(?Prefix, ?Suffix, ?List, ?Length)
%   is true when
%	append(Prefix, Suffix, List) &
%	length(Prefix, Length).

Rewriting this predicate from scratch, we get

    append_length(P, S, L, N) :-
	(   integer(N) ->
	    N >= 0,
	    'append length 1'(N, P, S, L)
	;   var(N) ->
	    'append length 1'(P, S, L, 0, N)
	;   error
	).

    'append length 1'([], L, L, N, N).
    'append length 1'([H|T], L, [H|R], N0, N) :-
	    N1 is 1+N0,
	    'append length 1'(T, L, R, N1, N).

    'append length 1'(0, T, L, R) :- !,
	    T = [], L = R.
    'append length 1'(N, [H|T], L, [H|R]) :-
	    M is N - 1,
	    'append length 1'(M, T, L, R).

We put this in our library and forget the implementation.
It is easy to remember what it means and what the argument order is;
the predicate name says it all.

Now,
	append_length(N, A, Z, OriginalList)
will split the original list in two.  It will not copy Z.  It will make
a new copy of A, but we need that for the end of the new list.
	append(Z, A, RotatedList)
will copy the cells of Z onto the front of RotatedList, but that is just
what we need.  So we get

    rotate(List, Shift, Rotated) :-
	    Shift >= 0,
	    !,
	    append_length(Shift, A, Z, List),
	    append(Z, A, Rotated).
    rotate(List, Shift, Rotated) :-
	    OppositeShift is -Shift,
	    append_length(OppositeShift, A, Z, Rotated),
	    append(Z, A, List).

_Is_ there anything to gain by avoiding the use of append/3 here?
No, nothing.  We have to copy all of the cells of the original list.
List differences don't always pay off.