🚀 go-pugleaf

I am learning the language too. But, I got the following idea.
I am looking for any more elegant solution...

FYI.

-Taro Yamamot
tyamamot@adobe.com

rotate(List, Shift, RotatedList) :-
	Shift > 0, !,
		length(List, TotLen), Shift2 is TotLen - Shift,
		rot(List, Shift2, RotatedList).

rotate(List, Shift, RotatedList) :-
	Shift < 0, !,
		Shift2 is -Shift,
		rot(List, Shift2, RotatedList).			

rot(List, Shift, RotatedList) :- !,
	append(SubList1, SubList2, List), length(SubList2, Len), Len =:= Shift, !,
	append(SubList2, SubList1, RotatedList).

rot(List, Shift, RotatedList) :-
		length(List, Len),
		Shift2 is Len - Shift, !, rot(List, Shift2, RotatedList).



Disclaimer:  
Views and recommendations, express or implied, are my own, and
do not reflect the opinion or policy of my employers.

tyamamot (Taro Yamamoto) writes:

>I am learning the language too. But, I got the following idea.
>I am looking for any more elegant solution...
Arent we all :-)

>FYI.

>-Taro Yamamot
>tyamamot@adobe.com

>rotate(List, Shift, RotatedList) :-
>	Shift > 0, !,
>		length(List, TotLen), Shift2 is TotLen - Shift,
>		rot(List, Shift2, RotatedList).
I would not recommend the use of length

>rotate(List, Shift, RotatedList) :-
>	Shift < 0, !,
>		Shift2 is -Shift,
>		rot(List, Shift2, RotatedList).			

>rot(List, Shift, RotatedList) :- !,
>	append(SubList1, SubList2, List), length(SubList2, Len), Len =:= Shift, !,
>	append(SubList2, SubList1, RotatedList).
or append
>rot(List, Shift, RotatedList) :-
>		length(List, Len),
>		Shift2 is Len - Shift, !, rot(List, Shift2, RotatedList).

To avoid length, just let the items of a list go by.
To avoid append, use difference lists.

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).

It should work both ways.

Greetings

Arjen

In article <9210122012.AA08759@enuxha.eas.asu.edu>, gomez@enuxha.eas.asu.edu (JL Gomez) writes:
> I've been learning PROLOG and building up some list predicates.

This sounds as though you are saying that you _have_ written subseq/2
and rotate/3.  But from the rest of the posting it sounds as though
you want help in writing them.

%   subseq(Sub, Seq) is true if
%   Sub and Seq are lists and Sub is a subsequence of Seq.
%   (This corresponds to subseq0(Seq, Sub) in the Quintus library(lists).)

subseq([], _).			% empty is a subsequence of everything.
subseq([H|Sub], Seq) :-		% nonempty must come from Seq.
	append(_, [H|R], Seq),	% skip over a prefix of Seq, pick up H,
	subseq(Sub, R).		% and recur on what is left.

%   You can improve that a bit; the call to append/3 will construct a
%   list which we then ignore.  So we can do

skip_prefix([H|R], H, R).
skip_prefix([_|L], H, R) :-
	skip_prefix(L, H, R).

subseq([], _).
subseq([H|T], S) :-
	skip_prefix(S, H, R),
	subseq(T, R).

> 
> The others are rotate predicates like:
> 
> rotate([a,b,c,d,e],2,X).
> X = [c,d,e,a,b]
> 
> which rotates right, and then
To me that is a LEFT rotation; the elements of the list moved left.
(When they reached the left edge they wrapped around to the right,
but that is another matter.  If they were bits in a register with
the most significant bit at 'a' and the least significant bit at 'e'
this would involve a "rotate LEFT" instruction.)
> 
> rotate([a,b,c,d,e,f],-2,X]
> X = [e,f,a,b,c,d]
> 
> rotates left.
To me that is a RIGHT rotation; the elements of the list moved right.
(When the reached the right edge they wrapped around to the left,
but that is another matter.
Let's draw a before and after picture:
To rotate by +N:
	+---+---+      +---+---+
	| A | Z |  =>  | Z | A |
	+---+---+      +---+---+
where length(A) = N.  To rotate by -N, the same picture, but length(Z) = N.

So,
rotate(List, Amount, Result) :-
	length(List, Total),
	(   Amount >= 0 ->
	    Prefix is Amount
	;/* Amount < 0 */
	    Prefix is Total + Amount
	),
	Prefix =< Total,
	length(A, Prefix),
	append(A, Z, List),
	append(Z, A, Result).

I wrote similar predicates a long while ago, but although I found it
instructive to do so (most list processing predicates are _easy_ if
you draw a few pictures and think "append") I've never since found
any actual use for them.

For what it's worth, here's how I'd _really_ do rotate/3:

rotate(Amount, Original, Rotated) :-
	same_length(Original, Rotated, Length),
	    %	same_length/3 comes from library(lists).  Very handy.
	T is -Length,
	between(T, Length, Amount),
	    %   between/3 comes from library(between).  VERY handy.
	(   Amount >= 0 -> Prefix is Amount
	;/* Amount < 0 */  Prefix is Length + Amount
	),
	length(A, Prefix),
	append(A, Z, Original),
	append(Z, A, Rotated).

You can even call that with all its arguments unbound and it will
enumerate all the logical solutions.

In article <9210122012.AA08759@enuxha.eas.asu.edu> gomez@enuxha.eas.asu.edu (JL Gomez) writes:
>I've been learning PROLOG and building up some list predicates.
> 
>One of them is a subsequence predicate which returns yes if the elements
>in the first list match the elements in the second list.
>
>The others are rotate predicates like:
>
>rotate([a,b,c,d,e],2,X).
>X = [c,d,e,a,b]
>
>which rotates right, and then
>
>rotate([a,b,c,d,e,f],-2,X]
>X = [e,f,a,b,c,d]


	% true if Sub is a "subsequence" (not necessarily contiguous)
	% of Seq
subseq([], _).
subseq(A.Sub, A.Seq) :-
	subseq(Sub, Seq).
subseq(Sub, _.Seq) :-
	subseq(Sub, Seq).

	% rotates list to right or left (shift can be negative)
rotate(List, Shift, RotatedList) :-
	length(List, Len),
	LenH is (Shift + Len) mod Len,
	length(H, LenH),
	append(H, T, List),
	append(T, H, RotatedList).

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.