% T-93.540 Logiikkaohjelmointi, syksy 2003 % Handson exercises part 1, Prolog % 26.9.2003 % Martti Meri % Code in Prolog the following predicates. % You can find the exact specification for % the predicate in the swi-prolog manual % (see sections on List Manipulation and Set % manipulation. In this exercise the % predicate names are prefixed with my-prefix. % the member predicate is thus here named % mymember. % The prototypes for the predicate present % the argument usage % +Arg input argument , must be fully instantiated % -Arg output argument % ?Arg maybe instantiated to varyin degree % Below you will also find some tests to run on % the predicates. % 1. member-predicate % mymember(?Elem, ?List) % succeeds if Elem is in the List. mymember(Y,[H |_]) :- H = Y. mymember(_,[]) :- !,fail. mymember(Y,[_ | T]) :- mymember(Y,T). % TESTS: % mymember(b,[a,b,c]). % mymember(X,[a,b,c]). % mymember([A,b],[[a,X],c,d]). % 2. reverse % myreverse(+List1,-List2) myreverse([],C,C). myreverse([H1 | T1],R,C) :- myreverse(T1,[H1 | R],C). myreverse(A,C) :- myreverse(A,[],C). % TESTS: % % myreverse([a,b,c],A). % 3. set_merge % mymerge_set(+Set1,+Set2,-Set2) % Set1 and Set2 without duplicates sorted in standard order % Set3 is unified with an ordered set without dublicates. mymerge_set1([],C,C). mymerge_set1([H|T],B,C) :- mymember(H,B), !, mymerge_set1(T,B,C). mymerge_set1([H|T],B,C) :- mymerge_set1(T,[H|B],C). mymerge_set(A,B,C) :- myreverse(A,A1), mymerge_set1(A1,B,C). % TESTS: % mymerge_set([a,b,c],[b,c,d],C). -> C = [a, b, c, d]. % note the result below is according to the specs. % mymerge_set([a,b,b],[b,c],D). -> D = [a, b, b, b, c]. % 4. length % my_lengt(?List, ?Int) % Int is the length of the list List mylength1(N,[],N):-!. mylength1(N,[_ | T],L) :- NP is N+1, mylength1(NP,T,L). mylength(A,L) :- mylength1(0,A,L). % TESTS: % mylength([a,b,c],C). -> 3 % mylength(A,3). -> [_G1, _G2, _G3] % mylength([a,X,C],C). -> X = _G4, C = 3 % mylength([a,3,b,[a,b]],R). -> R = 4 % 5.Sorting % 5.a sort % mysort(+List,-SortedList) % sorting is done in standard order of terms % (see manuals and examples below). % Use @> , @< , @<= and @>= -predicates % that have arity 2 for testing order of two terms. mysort1([],[]). mysort1([H1],[H1]). mysort1([H1,H2|T1],[H1|T2]) :- H1 @< H2, !, mysort1([H2 |T1],T2). mysort1([H1,H2|T1],[H2|T2]) :- H1 @>= H2, !, mysort1([H1|T1],T2). mysort2(0, S, S). mysort2(L, A, S) :- mysort1(A,S1), LM is L - 1, mysort2(LM,S1,S). mysort(A, S) :- mylength(A,L), mysort2(L,A,S), !. % TESTS: % mysort([[a,b],3,b,2,a],L). -> L = [2, 3, a, b, [a, b]] % 5.a quicksort % Program 3.32 (Quicksort) in Sterling &Shapiro % The predicate uses partition-predicate partition([X|Xs],Y,[X|Ls],Bs) :- X @< Y, partition(Xs,Y,Ls,Bs). partition([X|Xs],Y,Ls,[X|Bs]) :- X @>= Y, partition(Xs,Y,Ls,Bs). partition([],_,[],[]). % quicksort myquicksort([X|Xs],Ys) :- partition(Xs,X,Littles,Bigs), myquicksort(Littles,Ls), myquicksort(Bigs,Bs), append(Ls,[X|Bs],Ys). myquicksort([],[]). % TESTS: % myquicksort([e,b,a,d,c],Y). %6. union % myunion(+Set1,+Set2,-Set3) % Set3 is the union of Set1 and Set2. % The spec requires that Set1 and Set2 are lists without % duplicates, but lets define myunion so that they have % duplicates. myunion(A,B,C) :- mymerge_set(A,[],C1), mymerge_set(B,C1,C2), mysort(C2,C). % TESTS: % myunion([a,b,c],[b,d,e,e],C). -> [a, b, c, d, e] % myunion([c,b,a],[a,b,c],C). -> [a, b, c] % note the following is not required (causes stack overflow.) % myunion([X,Y,Z],[b,d,e,e], [a, b, c, d, e]). 7. Difference lists append_dl([P,Q1],[Q2,R],[P, R]) :- Q1 = Q2. % append_dl([[a,b,c],Xs],[[b,c,d],[d]],Zs). % append_dl([[a,b,c,d,e],Xs],[[b,c,d,e],[d,e]],Zs). member_dl(R,[P,Q]) :- mymember(R,P), \+mymember(R,Q). % TESTS: % member_dl(X,[[a,b,c],[c]]). -> X= a ; X = b my2reverse(Xs,Ys) :- reverse_dl(Xs,[Ys,[]]). reverse_dl([X|Xs],[Ys,Zs]) :- reverse_dl(Xs,[Ys,[X |Zs]]). reverse_dl([],[Xs,Xs]). % How can you code quick sort using difference lists? my2quicksort(Xs,Ys) :- write('Sterling and Shapiro program 15.4 Quicksort using difference lists,'),nl,ttyflush, quicksort_dl(Xs,[Ys,[]]). quicksort_dl([X|Xs],[Ys,Zs]) :- partition(Xs,X,Littles, Bigs), quicksort_dl(Littles,[Ys,[X|Ys1]]), quicksort_dl(Bigs,[Ys1,Zs]), write('tree '),write([X,Ys1,Ys,Zs]),nl,ttyflush. quicksort_dl([],[Xs,Xs]):- write('leaf '),write(Xs),nl,ttyflush. % TEST % my2quicksort([a,c,e,d,b],Y). -> Y = [a, b, c, d, e] ; % my2quicksort([a,[c,e],d,b],Y). -> Y = [a, b, d, [c, e]] ; % my2quicksort([c,b,e,a,d],Y). -> Y = [a, b, c, d, e] % my2quicksort([c,X,e,a,d],[a,b,c,d,e]). -> No % my2quicksort([h,m,a,k,t,u,v,e,q,p,t,n,f,l,u,i,c,z],L). % L = [a, c, e, f, h, i, k, l, m, n, p, q, t, t, u, u, v, z] % ?- my2quicksort([h,m,a,k,t,u,v,e,q,p,t,n,f,l,u,i,c,z],L). % leaf [a|_G778] % leaf [c|_G808] % leaf [e|_G799] % tree [c, [e|_G799], [c, e|_G799], [e|_G799]] % leaf [f|_G841] % leaf [h|_G760] % tree [f, [h|_G760], [f, h|_G760], [h|_G760]] % tree [e, [f, h|_G760], [c, e, f, h|_G760], [h|_G760]] % tree [a, [c, e, f, h|_G760], [a, c, e, f, h|_G760], [h|_G760]] % leaf [i|_G958] % leaf [k|_G949] % tree [i, [k|_G949], [i, k|_G949], [k|_G949]] % leaf [l|_G991] % leaf [m|_G934] % tree [l, [m|_G934], [l, m|_G934], [m|_G934]] % tree [k, [l, m|_G934], [i, k, l, m|_G934], [m|_G934]] % leaf [n|_G1096] % leaf [p|_G1087] % tree [n, [p|_G1087], [n, p|_G1087], [p|_G1087]] % leaf [q|_G1075] % tree [p, [q|_G1075], [n, p, q|_G1075], [q|_G1075]] % leaf [t|_G1060] % tree [q, [t|_G1060], [n, p, q, t|_G1060], [t|_G1060]] % leaf [t|_G1186] % leaf [u|_G1177] % tree [t, [u|_G1177], [t, u|_G1177], [u|_G1177]] % leaf [u|_G1234] % leaf [v|_G1225] % tree [u, [v|_G1225], [u, v|_G1225], [v|_G1225]] % leaf [z|_G1267] % leaf [] % tree [z, [], [z], []] % tree [v, [z], [u, v, z], []] % tree [u, [u, v, z], [t, u, u, v, z], []] % tree [t, [t, u, u, v, z], [n, p, q, t, t, u, u, v, z], []] % tree [m, [n, p, q, t, t, u, u, v, z], [i, k, l, m, n, p, q, t, t, u, u, v, z], []] % tree [h, [i, k, l, m, n, p, q, t, t, u, u, v, z], [a, c, e, f, h, i, k, l, m, n, p, q, t, t, u, u, v, z], []] % Also you can trace the execution of your programs by before launching them % giving trace command and after notrace command. ?- trace. ... notrace. % Standard output can be directed to a file by prior % tell call and a told call after. tell('myout'). told. % use help(tell(. for mote details.