🚀 go-pugleaf

If you are doing a lot of rotation and little appending and deletion,
you could reduce the time it takes to order(1) by changing your
representation. 

Suppose you represent a list by a term list(L,S,Xs) where L is the
number of things in the list, S is the current shift (initially zero)
and Xs are the items themselves, e.g. 

	list(4,0,[a,b,c,d])    is the list [a,b,c,d]
	list(4,1,[a,b,c,d])    is the list [b,c,d,a]
	list(5,2,[p,q,r,s,t])  is the list [r,s,t,p,q]

Some routines for accessing these structures follow.  You are welcome to
make free use of this code and to distribute it freely, but if you make
a profit I want a share. 


rotate(Rotation,list(L,S1,Xs),list(L,S2,Xs)) :-
	S2 is (Rotation + S1) mod L.

first(list(L,S,Xs),X) :-
	nth(S,Xs,X).

last(list(L,S,Xs),X) :-
	Index is (S + L) mod L,
	nth(Index,Xs,X).

Appending two of these things looks difficult, but the following might
work (I have not tested it)

append(list(L1,S1,Xs1),list(L2,S2,Xs2),list(La,0,Xsa)) :-
        append(1,L,list(L1,S1,Xs1),list(L2,S2,Xs2),X-X,Xsa-[]).

append(L,L,_,_,List,List).

append(N,L,list(L1,S1,Xs1),List2,X-[Item|Y],Xs_out) :-
        N =< L1,
        nth(N,list(L1,S1,Xs1),Item),
        N1 is N + 1,
        append(N1,L,list(L1,S1,Xs1),List2,X-Y,Xs_out).

append(N,L,list(L1,S1,Xs1),List2,X-[Item|Y],Xs_out) :-
        N > L1,
        N =< L,
        M is N - L1,
        nth(M,List2,Item),
        N1 is N + 1,
        append(N1,L,list(L1,S1,Xs1),List2,X-Y,Xs_out).


nth(N,list(L,S,Xs),X) :-
	Index is (N + S) mod L,
	nth(Index,Xs,X).

nth(1,[H|_],H).

nth(N,[_|T],X) :-
	N > 1,
	N1 is N - 1,
	nth(N1,T,X).



-- 
//// Advice to dieters:         ////  Ken Johnson, A I Applications Institute
////   Never eat more than      ////       80 South Bridge, EDINBURGH EH1 1HN
////   you can carry.           ////                 E-mail ken@aiai.ed.ac.uk
////              -- Miss Piggy ////     phone 031-650 2756  fax 031-650 6513