% Comp280, Spring 2000
% Solutions to homework 8
% Kathi Fisler; March 29, 2000

% member(Element, List)
% true if Element is in List

member(E, [E|_]).

member(E, [_|T]) :- member(E,T).

% putLast(Element,OldList,NewList) 
% true if NewList consists of the elements of OldList followed by Element.  

putLast(E,[],[E]).

putLast(E,[H|T],[H|L1]) :- putLast(E, T, L1).

% consecutive(X,Y,L) 
% true if X and Y are consecutive elements of list L. 

consecutive(X,Y,[X,Y|_]).

consecutive(X,Y,[_|T]) :- consecutive(X,Y,T).

% reverse(L1, L2)
% true if L2 is the reverse of L1

reverse([],[]).

reverse([H1|T1], L2) :- 
  putLast(H1, Temp, L2),
  reverse(T1, Temp).

% palindrome(L) 
% true if the list L is a palindrome (reads the same backwards and forwards). 
% this uses helper rule reverse

palindrome(L) :- reverse(L,L).

% rotate(L,N,R) 
% true if R is the result of rotating the list L by N steps to the right.  
% (e.g., rotate([a,b,c,d,e],2,[d,e,a,b,c]) is true).

rotate(L,0,L).

rotate(L1, N, [H|T]) :-
  N > 0,
  putLast(H,T,L2),
  N1 is N - 1,
  rotate(L1,N1,L2).

% permutation(L1,L2) 
% true if list L2 is a permutation of list L1

minus_elt(X,Y,[X|Y]).
minus_elt(X,[Y1|Y2],[Y1|Z]) :- minus_elt(X,Y2,Z).

permutation([X],[X]).
permutation([X|Y],Z) :- permutation(Y,Z1), minus_elt(X,Z1,Z).