There are no other operations on dolls and boxes.
- Write the ML signature that models a doll factory.
- Write a reference implementation: that is, an ML structure
that implements this signature as straightforwardly as possible.
In your reference implementation, creation of a doll or construction
of a box should just be the application of a data constructor.
- Write a structure that implements this signature more
efficiently.
For each type in the signature, use as efficient a representation as
possible, given the set of operations required.
- Prove the equivalence of your two implementations.
Please show the simulation relation ~
as precisely as you can.
Hint: Instead of defining ~ in closed form
the way the Queue relation R in lecture was defined,
you may give an inductive definition.
Note:
A baby doll weighs 10 grams.
A doll shell(baby) weighs 30 grams: 20 for the shell, 10 for the
baby.
The doll shell(shell(baby))
weighs 60 grams: 30 for the outer shell,
20 for the inner shell, 10 for the baby.
If I create
a = baby
b = shell(a)
c = baby
d = shell(c)
e = shell(d)
Then I can create a box with the list [b,e].