<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
% 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). -&gt; C = [a, b, c, d].
%  note the result below is according to the specs.
%  mymerge_set([a,b,b],[b,c],D).  -&gt; 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).    -&gt; 3
% mylength(A,3).          -&gt; [_G1, _G2, _G3]
% mylength([a,X,C],C).    -&gt; X = _G4, C = 3
% mylength([a,3,b,[a,b]],R). -&gt; R = 4

% 5.Sorting
% 5.a sort
% mysort(+List,-SortedList)
% sorting is done in standard order of terms
% (see manuals and examples below).
% Use @&gt; , @&lt; , @&lt;= and @&gt;= -predicates
% that have arity 2 for testing order of two terms.

mysort1([],[]).
mysort1([H1],[H1]).

mysort1([H1,H2|T1],[H1|T2]) :-
    H1 @&lt; H2,
    !,
    mysort1([H2 |T1],T2).

mysort1([H1,H2|T1],[H2|T2]) :-
    H1 @&gt;= 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).  -&gt; L = [2, 3, a, b, [a, b]] 

% 5.a quicksort
% Program 3.32 (Quicksort) in Sterling &amp;Shapiro
% The predicate uses partition-predicate

partition([X|Xs],Y,[X|Ls],Bs) :-
   X @&lt; Y,
   partition(Xs,Y,Ls,Bs).

partition([X|Xs],Y,Ls,[X|Bs]) :-
   X @&gt;= 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). -&gt; [a, b, c, d, e] 
% myunion([c,b,a],[a,b,c],C). -&gt;  [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]]).  -&gt;  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).   -&gt;   Y = [a, b, c, d, e] ;
% my2quicksort([a,[c,e],d,b],Y).   -&gt;  Y = [a, b, d, [c, e]] ;
% my2quicksort([c,b,e,a,d],Y). -&gt; Y = [a, b, c, d, e] 
% my2quicksort([c,X,e,a,d],[a,b,c,d,e]). -&gt; 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.
</pre></body></html>