Applying Logical Knowledge

Turkish Dolls

Turkish dolls are like Russian dolls, except they have two compartments. In the left-hand one there can be anything, like an apple, pear, plum, or cherry. The right is a special compartment that can only hold another turkish doll.

There is a wooden Turkish doll for the right side when there is no more nesting.

A Turkish doll is represent by the structure c/2. The wooden doll is represented by c. Here is a nested turkish doll with four fruits in it.

c(apple, c(pear, c(plum, c(cherry, c))))

c_test(-C)
C - a test doll from above.

?- c_test(C).
C = c(apple,c(pear,c(plum,c(cherry,c))))
yes

Note that a simple query can be used to find the first item in the doll, and the nested doll of remaining items:

?- c_test( c(FIRST, REST) ).
FIRST = apple
REST = c(pear, c(plum, c(cherry, c)))
yes

Take special note of the fact that the first argument of c/2 is ALWAYS an item, and the second argument is ALWAYS another doll, or the empty doll.

In other words, the second argument can always be fed back into a recursive predicate. However, these first three predicates require nothing more than a simple fact.

c_first_item(+C, -ITEM)
C - the nested doll
ITEM - the outermost, first item in the doll
hint: this can be done with a single fact.

?- c_test(C), c_first_item(C, X).
C = c(apple,c(pear,c(plum,c(cherry,c))))
X = apple
yes

c_add_first_item(+ITEM, +C1, -C2)
ITEM - the item to add as new first/outermost doll
C1 - the initial nested doll
C2 - the output nested doll with new item
hint: this can be done with a single fact.

?- c_test(C), c_add_first_item(beer, C, C2).
C = c(apple,c(pear,c(plum,c(cherry,c))))
C2 = c(beer,(c(apple,c(pear,c(plum,c(cherry,c)))))

c_delete_first_item(+C1, -ITEM, -C2)
C1 - the initial nested doll
ITEM - the item that was deleted
C2 - the output nested doll with new item
hint: this can be done with a single fact.

?- c_test(C), c_delete_first_item(C, X, C2).
C = c(apple,c(pear,c(plum,c(cherry,c))))
X = apple
C2 = c(pear,c(plum,c(cherry,c)))))

c_length(+C, -L)
C - the input doll
L - the number of items in the doll
hint: use an accumulator. the boundary condition is the wooden doll, c.

?- c_test(C), c_length(C,L).
C = c(apple,c(pear,c(plum,c(cherry,c))))
L = 4
yes

c_write(+C)
C - the input doll, whose things are to be written out.
hint: keep writing what you see and recursing with what's left.

?- c_test(C), c_write(C).
apple pear plum cherry
C = c(apple,c(pear,c(plum,c(cherry,c))))
yes

c_member(?ITEM, +C)
ITEM - an item to look for, or variable which will take the value of items found.
C - the input doll.

c_member can test if something is in a doll:

?- c_test(C), c_member(pear, C).
C = c(apple,c(pear,c(plum,c(cherry,c))))
yes

or generate on backtracking all of the items in a doll:

?- c_test(C), c_member(X,C).
C = c(apple,c(pear,c(plum,c(cherry,c))))
X = apple ;
C = c(apple,c(pear,c(plum,c(cherry,c))))
X = pear ;
C = c(apple,c(pear,c(plum,c(cherry,c))))
X = plum ;
C = c(apple,c(pear,c(plum,c(cherry,c))))
X = cherry ; 
no

c_reverse(+C, -CR)
C - an input doll
CR - an output doll, with items in reverse order
hint: use an accumulator to build the output doll, it will be automatically reversed when it gets to the boundary condition.

?- c_test(C), c_reverse(C, CR).
C = c(apple,c(pear,c(plum,c(cherry,c))))
CR = c(cherry,c(plum,c(pear,c(apple,c))))
yes

c_append(?C1, ?C2, ?C)
C1 - a doll
C2 - another doll
C - a doll that is composed of C1's items followed by C2's items.
hint: work from the head (thing) of C1, leaving C2 pretty much alone. the boundary condition says if C1 is the wooden doll, then the answer, C, is just C2.

here's c_append making a double length copy from two copies of the test case.

?- c_test(C1), C2 = C1, c_append(C1,C2,C).
C1 = c(apple,c(pear,c(plum,c(cherry,c))))
C2 = c(apple,c(pear,c(plum,c(cherry,c))))
C = c(apple,c(pear,c(plum,c(cherry,c(apple,c(pear,c(plum,c(cherry,c))))))))
yes

here's c_append splitting the test doll into all possible splittings.

?- c_test(C), c_append(C1, C2, C).
C1 = c
C2 = c(apple,c(pear,c(plum,c(cherry,c)))) ;

C1 = c(apple,c)
C2 = c(pear,c(plum,c(cherry,c))) ;

C1 = c(apple,c(pear,c))
C2 = c(plum,c(cherry,c)) ;

C1 = c(apple,c(pear,c(plum,c)))
C2 = c(cherry,c) ;

C1 = c(apple,c(pear,c(plum,c(cherry,c))))
C2 = c ;
no

ROMANIAN DOLLS

Romanian dolls are like Turkish dolls, except they have three compartments. The first is for whatever thing might be there. The second and third are both Romanian dolls. The second might have things less than the thing, and the third might have things more than the thing.

In other words, a tree structure. If the nodes are left as variables, that is, open, then they can be filled in later.

So for example this structure

d(apple,L1,d(pear,d(cherry,L2,R2),d(plum,L3,R3)))

is the tree:

   apple
   /   \
  ?    pear
       /  \
   cherry plum
    / \   / \
   ?   ? ?   ?

The ? are open variables, that can be filled in (unified) with new branches of the tree.

d_test(-D)
D - a test tree, the one above.

?- d_test(D).
D = d(apple,H35,d(pear,d(cherry,H43,H44),d(plum,H47,H48)))
yes

d_write(+D)
D - a tree to display left to right
hint: if the tree is a variable, then that's the end of a branch. to test if X is a variable, use the built-in predicate var(X). the recursive case writes out the left side first, then the thing, then the right side.

?- d_test(D), d_write(D).
apple cherry pear plum
D = d(apple,H43,d(pear,d(cherry,H51,H52),d(plum,H55,H56)))
yes

d_store(+ITEM, ?D)
ITEM - a thing to put in the tree, in alphabetical sequence.
D - a growing open tree
hint: the boundary condition simply creates a new tree node, with the item as the thing in the node. there are two recursive cases, depending on whether the item sorts higher or less than the thing in the node being examined. use @< and @> to compare an item with the thing in the current node. note: make sure you put a ! in the boundary case, to stop it from going wild unifying variables with variables ad infinitum on backtracking.

use this predicate, d_loop/1 to test d_store/2.

d_loop(D) :-
   write('item? '),
   read(ITEM),
   d_store(ITEM, D),
   ITEM \= quit,
   d_loop(D).
d_loop(D).

?- d_loop(D), d_write(D).
item? apple.
item? pear.
item? plum.
item? cherry.
item? quit.
apple cherry pear plum
D = d(apple,H89,d(pear,d(cherry,H480,H481),d(plum,H336,H337)))
yes

Applying Logical Knowledge

Turkish Dolls

ROMANIAN DOLLS

Copyright ©2005 Amzi! inc.