Breadth-first tree traversal

For this example, we shall define trees as `rose trees':

     type rose_tree alpha == alpha # list(rose_tree alpha);

A tree consists of a label and a list of sub-trees. (Note that this particular implementation permits recursive type synonym definitions.)

We wish to construct the list the labels in breadth-first order. The method used is:

1.

Construct an infinite list of levels of the tree:

• The first level comprises just the input tree.
• Each other level consists of all the children of the previous level.

2.

Truncate the list before the first empty level.

3.

Concatenate the levels.

4.

Extract the labels of the trees.

This is represented directly, using ` .' to stand for reversed function application.

     uses lists, functions, products;

     dec bf_list : rose_tree alpha -> list alpha;
     --- bf_list t <= [t].
             iterate (concat o map snd).
             front_with (/= []).
             concat.
             map fst;

     bf_list (1, [(2, [(5, []),
                       (6, [(10, [])])
                      ]),
                  (3, [(7, [])]),
                  (4, [(8, [(11, [])]),
                       (9, [])
                      ])
                 ]);