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:
  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, [])
                      ])
                 ]);



Ross Paterson <ross@soi.city.ac.uk>