T-93.540 Logic Programming, Autumn 2005

Martti Meri
12.9.2005

Hands on exercises part 1, Prolog

Answers : see the link at the end of the page.

Code in Prolog the following predicates. You can find the exact specification for the predicates in the swi-prolog manual (see sections on List Manipulation and Set manipulation Reference manual). In this exercise the predicate names are prefixed with my-prefix. the member predicate is thus here named mymember. Use primitive operations in traversing and constructing the lists.

Example:

positives([],[]).
positives([H1 | T1],[ H1 | T2]) :-
   H1 > 0,
   !,
   positives(T1,T2).
positives([_ | T1],T2) :-
   positives(T1,T2).

Note: the underscore _ in the last version of the predicate
is used to mark the head of the list because if a variable
is not needed there, because the variable is not unified
to anything in the argument list or the body.

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.

  TESTS:
  mymember(b,[a,b,c]).
  mymember(X,[a,b,c]).
  mymember([A,b],[[a,X],c,d]).

2. reverse

 myreverse(+List1,-List2)

   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.
 

  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


  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.

  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([],_,[],[]).

 implement quicksort!


  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.
   
  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.

  TESTS:
 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).


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?

 Sterling and Shapiro program 15.4 - Quicksort using difference lists.


 TEST
 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([c,X,e,a,d],[a,b,c,d,e]). -> No


 You can use trace and notrace to see what happens
 ?-  trace.

 ?-  my2quicksort([h,m,a,k,t,u,v,e,q,p,t,n,f,l,u,i,c,z],L). 

... swi-prologs prompts a trace line and you press RETURN ...

 notrace.

 or you can add write(+Term),nl,ttyflush, lines in the code to 
 get output on the terminal.

8. Best first search

Heuristic search is a way to tackle complexity problems. Get acquainted to the techniques used in the following search algorithm. Best first search ).

ANSWERS TO EXERCISES..

Paluu/ylöspäin