Intro

A matryoshka doll [mɐˈtrʲɵʂkə], also known as a Russian nesting doll, Stacking dolls, or Russian doll is a set of wooden dolls¹ of decreasing size placed one inside another. The name “matryoshka” (матрёшка), literally “little matron”, is a diminutive² form of Russian female first name “Matryona” (Матрёна) or “Matriosha”.

A set of matryoshkas consists of a wooden figure which separates, top from bottom, to reveal a smaller figure of the same sort inside, which has, in turn, another figure inside of it, and so on.

The first Russian nested doll set was made in 1890 by Vasily Zvyozdochkin³ from a design by Sergey Malyutin⁴, who was a folk crafts painter at Abramtsevo⁵. Traditionally the outer layer is a woman, dressed in a sarafan⁶, a long and shapeless traditional Russian peasant jumper dress⁷. The figures inside may be of either gender; the smallest, innermost doll is typically a baby turned from a single piece of wood. Much of the artistry is in the painting of each doll, which can be very elaborate. The dolls often follow a theme; the themes may vary, from fairy tale⁸ characters to Soviet leaders⁹. In the west, Matryoshka dolls are often mistakenly referred to as “babushka dolls”, babushka meaning “grandmother” or “old woman”.

There is a large variety of Russian nesting dolls¹⁰. If you have dolls of more than one theme, it is possible to nest them incorrectly…

Exercise

Write a predicate ma_clean(+Mess, -Order) that converts a list Mess of malformed Matryoshka dolls into a list of alphabetically ordered well-composed dolls.

Representation of the dolls

A doll of type Type met size Size that contains an other doll Child is represented as: ma(Props, Child). Where Props is a list with exactly one occurrence of both type(Type) and size(Size). This list may also contain other information that may be ignored. If a doll has no child, empty is used as Child.

Example

The image above shows the transformation of

[
  ma([type(red),size(4)], ma([type(green),size(3)], empty) ),
  ma([size(3),type(blue)], ma([size(2),type(citron)], empty) ),
  ma([type(citron),size(4)], ma([type(citron),size(3)], ma([type(red),size(2)],empty)) ),
  ma([type(blue),size(4)], ma([type(green),size(2)], empty) ),
]

into

[
  ma([type(blue),size(4)],ma([size(3),type(blue)],empty)),
  ma([type(citron),size(4)],ma([type(citron),size(3)],ma([size(2),type(citron)],empty))),
  ma([type(green),size(3)],ma([type(green),size(2)],empty)),
  ma([type(red),size(4)],ma([type(red),size(2)],empty))
]

Hint

You may want to use ma_order(-Pred, +Doll1, +Doll2) that has been predefined for you in this database¹¹. it might be useful in combination with predsort/3¹². For it to work, it requires the availability of 2 other predicates that you should define: ma_type(+Doll,-Type) and ma_size(+Pop,-Size) that return the Type and Size of a doll. Do not alter the definition of ma_order/3, you don’t need to add it to your solution.