Applying Logical Knowledge

  Russian Dolls

Russian dolls are the ones that nest within each other. At the center is a wooden doll.

For these exercises, a Russian doll is represented as a(_). So it is a structure with something in it. The wooden doll is represented by the atom 'a'. For example, a triple nested doll looks like:

a(a(a(a)))

Write the following predicates:

a_test(-A)
A - a test doll with three dolls and the wooden doll in the last.
hint: this is a simple fact.

?- a_test(A).
A = a(a(a(a)))
yes

Note that a simple query can find the inside of the test doll, which is ALWAYS another doll or the wooden doll. This means it can be used to feed a recursive predicate.

?- a_test( a(X) ).
X = a(a(a))
yes

a_count(+A,-N)
A - the input doll
N - the output count
hint: use an accumulator and a second predicate a_count/3. the boundary condition will be the wooden doll

?- a_count(a, N).
N = 1
yes

?- a_test(A), a_count(A,N).
A = a(a(a(a)))
N = 4
yes

a_nest(?A1, ?A2)
A1 - the outer nested dolls
A2 - the inner nested dolls
hint: this is done with a simple fact that does it work through unification.

?- a_test(A), a_nest(A, A2).
A = a(a(a(a)))
A2 = a(a(a))
yes

?- a_test(A), a_nest(A2, A).
A = a(a(a(a)))
A2 = a(a(a(a(a))))
yes

a_build(+N, -A)
N - the number of levels of nesting.
A - the output doll, nested N deep.
hint: do not use an accumulator. boundary condition is when count is 1, and the answer then is the wooden doll. recursive calls recurse to fill in building structure.

?- a_build(1,A).
A = a
yes

?- a_build(5,A).
A = a(a(a(a(a))))
yes

A Greek doll is just like a Russian doll, but is represented by the letter b. This predicate makes a Greek copy to the same level of nesting as an input Russian doll.

ab_copy(?A, ?B)
A - a Russian doll, either input or out.
B - a Greek doll, either output or in.
hint: simple recursion, no tricks.

?- a_test(A), ab_copy(A,B).
A = a(a(a(a)))
B = b(b(b(b)))
yes

We don't have to put the wooden doll in as the last thing. How about if we can hide anything we want in the inner-most doll?

a_hide(+N, +PRIZE, -A)
N - the number of nested dolls
PRIZE - the thing in the middle
A - the output doll
hint: this might look like a_build, but isn't. you need an accumulator that starts with the prize and wraps layers as it goes down. but note that the second argument is that accumulator, seeded with the prize.

?- a_hide(3, plum, A).
A = a(a(a(plum)))
yes

note: when called with nesting of 0, there are no dolls, just the prize.

?- a_hide(0, plum, A).
A = plum
yes

Is it covered against run-away behavior on backtracking?

?- a_hide(3, plum, A).
A = a(a(a(plum))) ;
no

a_prize(+A, -PRIZE)
A - some input doll
PRIZE- the thing hidden in the middle
hint: keep peeling off layers and let the next call down find the prize. the boundary condition is when A is not a doll, or when A \= a(_).

?- a_hide(3, plum, A), a_prize(A, PRIZE). A = a(a(a(plum))) PRIZE = plum yes

OPEN DOLLS

Open is a technical term, meaning a structure with a variable in it that can be filled at a later time by unification. Open dolls are dolls using this idea.

With the dolls so far, we need to dig to find the prize. What if we were to keep open a shortcut to the inside? We could then access the inside directly.

We do this by using a slightly more complex data structure to represent the doll. It has two related terms, one being the full doll, and the other being the inside of the doll. They can be joined by the - operator for convenience. It looks like:

a(a(a(plum)))-plum

With this structure representing the doll, we can write predicates that get the plum directly, or peel the layers, as we please.

If we build an open doll with a variable inside, then we can fill the doll later just by unifying that variable with the contents. So if we had

a(a(a(X)))-X

by setting X = plum, we also put plum in the middle of the doll.

?- DOLL = a(a(a(X)))-X, X = plum.
DOLL = a(a(a(plum)))-plum
yes

Here's some predicates that illustrate this point, using 'open structures', or structures with a variable in them to begin with.

a_open_build(+N, -OA)
N - the input level of nesting
OA - the open Russian doll
hint: similar to a_build, but the boundary condition is when N = 1, and the doll is a(X)-X. note: this is the hardest of the open doll predicates to figure out.

?- a_open_build(3, A).
A = a(a(a(H53))) - H53
yes

a_open_hide(?OA, +PRIZE)
OA - an input open doll, prefaced with? because, although input, it is changed when its inner variable is unified.
PRIZE - the thing to put inside.
hint: a simple fact that does the work with unification.

?- a_open_build(3,A), a_open_hide(A,plum).
A = a(a(a(plum))) - plum
yes

note: once you've put something in the open doll you can't put a different thing in unless you backtrack over a_open_hide thus unbinding the variable:

?- a_open_build(3,A), a_open_hide(A,plum), a_open_hide(A,peach).
no

a_open_prize(+OA, -PRIZE)
OA - an input open doll, probably with its inner prize unified.
PRIZE - the thing found inside.
hint: the same predicate as a_open_hide.

?- a_open_build(3,A), a_open_hide(A,plum), a_open_prize(A,P).
A = a(a(a(plum))) - plum
P = plum
yes

Copyright ©2005 Amzi! inc.