Prolog Worksheet 2, due Monday, April 20

Problems for this Worksheet 2 with Prolog

1. Lists of Even Length: Write a Prolog rule for a list Lst that succeeds if and only if Lst has an even number of elements. Rather, think patterns and recursion!

   Notes:

   • An empty list has 0 elements, and 0 is an even number.
   • No need to actually count the number of elements on the list for this rule.

2. Elements in Even and Odd Positions within a List: Write a Prolog rule evensOddsList(Evens, Odds, Lst) which succeeds if Evens is a sublist of Lst containing (in order) the elements in even positions of Lst (using 0-based indexing), and Odds is a sublist containing the elements in odd positions.

   Examples

         evensOddsList([a,c,e], [b,d,f], [a,b,c,d,e,f]).
             yields true
         evensOddsList([[b,d,f], a,c,e], [a,b,c,d,e,f]).
             yields false
         evensOddsList(Evens, Odds, [a,b,c,d,e,f,g]).
             yields Evens == [a,c,e,g] and Odds == [b,d,g]
       

3. Merging Two Sorted Lists: Assuming Lst1 and lst2 are two lists with elements in ascending order, write a rule merge(Lst1, Lst2, Result that succeeds if Result is the list obtained when Lst1 and lst2 are merged into a single ordered list.

   Note:

   • A Prolog rule merge could use an approach similar to either merge function described in Haskell Worksheet 4, Problem 7.

4. Merge Sort: Use the evensOddsList rule of problem 2 and the merge rule from problem 3, to write a rule to perform a merge sort.

   Note:

   • A Prolog rule merge could use an approach similar the description given in in Haskell Worksheet 4, Merge Sort and Lazy Evaluation.

5. Search Trees: Draw Prolog search trees for the query

         reverse([a,b,c,d], W).
       

   where reverse is defined bu the following sets of rules.

   1.           reverse([ ], [ ]).
                reverse([A|X], Z :- reverse(X, Y), append(Y, [A]. Z).
              

   2.           reverse(X, Z) :- rev(X, [ ], Z).
                rev([ ], Y, Y).
                rev[A|X], Y, Z) :- rev(X, [A | Y], Z).
              

   Logistics

   • Drawing a search tree can be done with software document tools, and that is acceptable.
   • However, drawing a search tree by hand on paper seems more intuitive and practical.
     • If you draw a search tree by hand, be sure the diagram is neat and clearly legible.
     • Take a picture of the hand-drawn search tree (e.g., with a cell phone) or otherwise make a digital copy.
     • Attach the file, labeled "wksh2-lastname-search-tree", where lastname is your last name.

6. Intersection of Two List Parameters: Wrote a Prolog rule (with helper rules, if needed), that succeeds if the intersection of two given list parameters is empty—that is, if no element on the first list is an element anywhere in the second list.

Extra Credit Problem

7. Retrieving Elements of a List Before a Given Item: Write a Prolog rule beforeWord(Item, Lst, Result) which succeeds when Result contains exactly those elements of the list Lst (in order) which appear before the Item.

   Examples:

        beforeWord(is, [computer, science, is, fun], Result]
           ==>  [computer, science'
        beforeWord(math, [computer, science, is, fun], Result]
           ==> fails
     

   Notes:

   • beforeWord(Item, Lst, Result) can be written simply, with a single line.
   • If Item is not found on the list Lst, then the rule should fail.

created 10 April 2020 revised 13 April 2020
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.