🚀 go-pugleaf

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.