/* This file defines various handy relationships involving sets. Here 'set' actually means 'list', but it sounds better ... */ /* member(H,List). Is H one of the elements of List? */ member(H,[H|_]). /* yes, if its the first member! */ member(H,[_|T]) :- member(H,T). /* yes, if its in the tail. N.B. */ /* T will be a list. Note that you */ /* fail if you get to asking for */ /* member(H,[]) , since this doesnt */ /* match either clause's head */ /* intersect(A,B,I). I is the intersection of A and B */ intersect([H|T],B,[H|U]) :- member(H,B), /* if the answer's got H in it, then */ intersect(T,B,U). /* it must be in B */ intersect([_|T],B,U) :- intersect(T,B,U). /* If first clause failed, we can */ /* ignore the head of first list */ intersect(_,_,[]). /* If the second also failed, the */ /* intersection is empty. */ /* YES, this example IS difficult... */ /* get the first N elements. The goal will be written as get_n(L,Ans,N) where N should be instantiated to a number, L is the list and the answer will be unified with Ans */ get_n([],[],_). /* The trivial case */ get_n([X|L1],[X|Ans1],N) :- N > 0, N1 is N-1, get_n(L1,Ans1,N1). get_n(_,[],0). /* append on list to another. The goal will be written as append(L1,L2,Ans) where Ans is L1 stuck onto the front of L2 */ append([],L,L). /* The trivial case */ append([H|T],L,[H|U]) :- append(T,L,U). /* Again, not totally obvious. Try */ /* an example on paper.. */ /* reverse a list. The goal will be written as reverse(L1,L2) where L2 is the reverse of L1 */ reverse([],[]). /* The trivial case */ reverse([H|T],L) :- reverse(T,R), /* Reverse T to get R, then ... */ append(R,[H],L). /* .. put H on the end to get L */ /* reverse: A FANCIER WAY (does that mean "better"??). This involves a subsidiary predicate reverse_append, with 3 args, the idea being that you 'pour' the first list (L1) into the second argument, till the first one is empty. Then unify second with third, which is the answer. The second argument is in effect an internal convenience for holding intermediate answers - STUDY THIS EXAMPLE, IT'S AN INTERESTING CONCEPT */ reverse2(L1,L2) :- reverse_append(L1,[],L2). reverse_append([H|T],L,M) :- reverse_append(T,[H|L],M). reverse_append([],L,L). /* union of two lists. This involves a 'cut'. The goal has the form union(L1,L2,Ans) where Ans is the list of elements in L1 or L2 */ union([],X,X). /* The trivial case */ union([X|R],Y,Z) :- member(X,Y), /* This clause is to ensure that if */ !, /* X is both lists, we ignore its */ union(R,Y,Z). /* presence in the first list */ union([X|R],Y,[X|Z]) :- union(R,Y,Z).