Prolog Worksheet 3, due Wednesday, April 29

Problems for this Worksheet 3 with Prolog

As with all work in computer science, be sure you include your testing for each of these problems as part of your submission!

1. Permutations: In class, we discussed the following rule which indicates whether an Item is inserted somewhere within an initial list Initial to obtain a resulting list Result.

         insert(Item, Initial, Result) :- append(SubL1, SubL2, Initial), append(SubL1, [Item | SubL2],Result).
       

   Using this rule for the insertion of an item into a list to obtain an expanded list, write one or more rules myPermutation(List, Perm) which succeeds when Perm is a permutation of List. That is, List and Perm have exactly the same elements, but the ordering of the elements may or may not be different.

   Example: Starting with the list [1,2,3], Prolog would produce the following output (in some order):

           ?- myPermutation([1,2,3], Perm).
           Perm = [1, 2, 3] ;
           Perm = [2, 1, 3] ;
           Perm = [2, 3, 1] ;
           Perm = [1, 3, 2] ;
           Perm = [3, 1, 2] ;
           Perm = [3, 2, 1] ;
           false.
       

   Caution: Since the number of permutations of a list increases rapidly with the set's size, you likely will want to limit testing to lists of reasonably small size (e.g., 3, 4, or 5).

2. A Permutation Sort: At the end of our first week exploring Prolog, we discussed a rule that succeeded if the elements in a list were ordered in ascending order. One variation of the rule follows:

           ordered([]).
           ordered([X]).
           ordered([X,Y|Rest]) :- ordered([Y|Rest]), X @=< Y.
       

   1. Using the myPermutation rule(s) of Problem 1 and the rule for ordered, write one or more rules for permutationSort(List, OrderedList). In this sorting algorithm, one generates all permutations of an original List and stops when one of the permutations OrderedList is determined to be ordered.
   2. In considering the work required for a permutation sort, what can one say about its efficiency? That is, determine the efficiency of the permutation sort (Big-O) when applied to a list of n elements, and briefly justify your conclusion.

      Hint: The efficiency is not O(n!), where n! is n*(n-1*(n-1)*...*2*1.

3. Duplicate Items: Write a Prolog rule

     duplicate(Original, Duplicated)
       

   where each element on the Original list appears twice in a row on the Duplicated list.

   Notes:

   • Elements on Duplicated should appear in the same order as on Original—they just appear twice.
   • No additional list items should be included on Duplicated.

   Examples:

         duplicate([1,2,3,3,4], [1,1,2,2,3,3,3,3,4,4])
         ==> true
         duplicate([1,2,3],[1,2,3,1,2,3]).
         ==> false (the duplicated values are not directly after each other)
         duplicate([1,2,3],[1,1,2,2,3,3,4]).
         ==> false (the second list contains an element (4) not on the
         original list).
       

4. The British Royal Family Tree (contemporary), Continued: Problem 1 in Prolog Worksheet 1 involved facts and rules related to the British Royal Family, as described in the upper-left image of the family tree from tes.com (formerly The Times Educational Supplement and referenced by the BBC).

   Although the original Prolog file provided the necessary information about mothers, fathers, children, and spouses, the file was cumbersome. For example, each mother/child relationship formed a separate fact, and the collection of gender designations extended for 28 lines (not counting comments and blank lines for clarity).

   A more compact (and likely less error prone) approach formats the same information within a list structure. A first attempt at compacting might place the names of a list for a given descriptor, such as

      % women % % % % % % % % % % % % % % % % % % % % %
      femalePerson([elizabetyII, diana, camilla, anne, sarah, sophie]).
      femalePerson([kate, autumnPhillips, zaraTindall, beatrice, eugenie, louise]).
      femalePerson([charlotte, savannah, isla, miaGrace]).
   
      % men % % % % % % % % % % % % % % % % % % % % % %
      malePerson([philip, charles, markPhillips, timothyLaurence, andrew, edward]).
      malePerson([william, harry, peterPhillips, mikeTindall, james, george]).
       

   Although this use of lists is more concise and perhaps more readable, it still requires a separate classification (e.g., femalePerson and malePerson) for each gender. Further, with this approach, rules would need to be expanded if other sexual identities were to be added. This suggests that an identity might be added to the representation, so each group of people would be listed on a list, the first component of which was the identity and the second was a list of individuals. With this approach, gender might be recorded as follows:

       % women % % % % % % % % % % % % % % % % % % % % %
      [female, [elizabetyII, diana, camilla, anne, sarah, sophie]]
      [female, ([kate, autumnPhillips, zaraTindall, beatrice, eugenie, louise]].
      [female, [charlotte, savannah, isla, miaGrace]]
   
      % men % % % % % % % % % % % % % % % % % % % % % %
      [male, [philip, charles, markPhillips, timothyLaurence, andrew, edward]]
      [male, [william, harry, peterPhillips, mikeTindall, james, george]]
       

   Next, a sexualIdentity label could be included to store a list of these lists of categories and lists of people, as follows:

   sexualIdentity([  
                   [female, [elizabetyII, diana, camilla, anne, sarah, sophie]],
                   [female, [kate, autumnPhillips, zaraTindall, beatrice, eugenie, louise]],
                   [female, [charlotte, savannah, isla, miaGrace]], 
   
                   [male, [philip, charles, markPhillips, timothyLaurence, andrew, edward]],
                   [male, [william, harry, peterPhillips, mikeTindall, james, george]]
                ]).
       

   Similarly, relationships of mother/child and father/childe could be reorganized as a collection of [parent, [children..]] lists. One way this might be accomplished follows:

   %parents-children
   momChildList([[elizabethII, [charles, ann, andrew, edward]], [diana, [william, harry]]]).
   momChildList([[anne, [peterPhillips, zaraTindall]], [sarah, [beatrice, eugenie]]]).
   momChildList([[sophie, [louise, james]], [kate, [george, charlotte]]]).
   momChildList([[autumnPhillips, [savannah, isla]], [zaraTindall, [miaGrace]]]).
   dadChildList([[philip, [charles, anne, andrew, edward]], [charles, [william, harry]]]).
   dadChildList([[markPhillips, [peterPhillips, zaraTindall]], [andrew, [beatrice, eugenie]]]).
   dadChildList([[edward, [louise, james]], [william, [george, charlotte]]]).
   dadChildList([[peterPhillips, [savannah, isla]], [mikeTindall, [miaGrace]]]).
       

   File british-royal-family-lists.pl contains these revised facts and rules.

   Within this framework, write rules for the following:

   1. Relation motherChild(Mom, Child), which succeeds when Mom is the mother of Child. Thus, motherChild here gives the same results as the mother facts in Prolog Worksheet 1.
   2. Relation femalePers(Pers), which succeeds if Pers identifies as female. Thus, femalePers here gives the same results as the female facts in Prolog Worksheet 1.
   3. Write a similar relation malePers(Pers), which succeeds if Pers identifies as male.
   4. Relation oldestChildIsDaughter(Parent, Child), which succeeds if Child is a child of Parent, and if Child comes first on the parent's list of children, and if that child identifies as female. (Here, we assume that the list of child is ordered from oldest to youngest.)
   5. Relation oldestDaughter(Parent, Child), which succeeds if Child is a child of Parent, and if Child comes first on the parent's list of children among those who identify as female.
   6. Relation youngestChild(Parent, Child), which succeeds if Child is a child of Parent, and if Child comes last on the parent's list of children.

5. In reviewing your rules for Problem 4e,

   1. What happens if the conditions are placed in different orders? For example, what happens if femalePers is the first clause or the last clause? Explain briefly.
   2. The file of facts identifies each individual as either male or female, and each person has exactly one of these identities in the file. Now consider your answer to Problem 5a, and replace femalePers by not(male...). Experiment placing this alternative condition in various positions, just as in step 5a, describe what happens in each case, and briefly explain.

Extra Credit Problem

6. Expanding on Problems 4 and 5 above and using british-royal-family-lists.pl as the fact/rule base for the British Royal Family, write rules for the following.

   1. Write a query oldestSiblingIsFemale(Person), which succeeds (i.e., returns true), if the oldest sibling of Person is female and fails otherwise. (Note, the sibling must be different from the person.)
   2. Write a query oldestSister(Person, Sister), which is true if Person is a sibling of the code, the Person is different from the sibling, the sibling is female, and the sibling is the first female on the list of children (not counting the Person).

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