-- Representing a tree as a sequence of levels. Breadth-first numbering
--
-- We introduce a representation of a binary tree as a sequence of
-- levels, where level_i is a sequence of nodes at the distance of
-- exactly i from the root, in the breadth-first traversal order.
-- We define conversions to and from the level representation.
-- One application of the level representation is the breadth-first
-- numbering of trees, the problem posed by Chris Okasaki at ICFP00.
module BFN where
import Control.Monad.State
-- Our Tree data type, with values of the type a in leaves and nodes
data Tree a = Leaf a | Node a (Tree a) (Tree a)
deriving (Show,Eq)
-- Elements of the sequence level_i
data ZT a = LV a | NV a
deriving Show
-- The level representation of a tree, the sequence of levels
-- The following type is `large': it also includes sequences
-- of levels that correspond to no tree (i.e., not in the image of
-- bf_unzip below). For example, if a sequence of
-- level_i, 0* [Tree a]
-- below is partial. If we programmed in Agda, we could
-- defined BFZ in such a way that bf_zip is total.
type BFZ a = [[ZT a]]
-- Convert from a forest to a level representation
-- The following code emphasizes clarity over efficiency:
-- the folding by curr_level and next_level can be merged.
bf_unzip :: [Tree a] -> BFZ a
bf_unzip [] = []
bf_unzip forest = map curr_level forest :
bf_unzip (foldr next_level [] forest)
where
curr_level (Leaf x) = LV x
curr_level (Node x _ _) = NV x
next_level (Leaf _) acc = acc
next_level (Node _ t1 t2) acc = t1 : t2 : acc
-- A sample tree
tree1 = Node 1 (Node 2 (Leaf 3)
(Node 4 (Leaf 5)
(Leaf 6)))
(Node 12 (Node 14 (Leaf 15)
(Leaf 16))
(Leaf 13))
tu = bf_unzip [tree1]
-- The following corresponds to reading the values
-- of tree1 nodes column-wise, left-to-right
{-
[[NV 1],
[NV 2,NV 12],
[LV 3,NV 4,NV 14,LV 13],
[LV 5,LV 6,LV 15,LV 16]]
-}
-- Convert the level representation to a forest
-- The function is partial because the pattern-match in build
-- is not exhaustive. Some values of the type BFZ a correspond to
-- no tree (forest)
bf_zip :: BFZ a -> [Tree a]
bf_zip [] = []
bf_zip (l:t) = build l (bf_zip t)
where
build [] [] = []
build ((LV x):t) p = (Leaf x) : build t p
build ((NV x):t) (t1:t2:p) = (Node x t1 t2) : build t p
-- Invariant: bf_zip . bf_unzip == id_Tree
-- If bf_zip were total (if the data type (BFZ a) were not too large),
-- bf_unzip . bf_zip == id would have been true as well.
tz = bf_zip tu
test1 = tz == [tree1]
-- Label BFZ a in the BFS order
-- This is best seen as a level-by-level left-to-right
-- traversal, attaching labels to each ZT
bfz_label :: [label] -> BFZ a -> BFZ (label,a)
bfz_label labels bfz = evalState (mapM (mapM label_v) bfz) labels
where
label_v v = curr_label >>= \l ->
return $ case v of
LV x -> LV (l,x)
NV x -> NV (l,x)
curr_label = do
(l:ls) <- get
put ls
return l
tul = bfz_label [101..] tu
{-
[[NV (101,1)],
[NV (102,2),NV (103,12)],
[LV (104,3),NV (105,4),NV (106,14),LV (107,13)],
[LV (108,5),LV (109,6),LV (110,15),LV (111,16)]]
-}
-- Okasaki's problem: BFS labeling of trees
bf_label :: [label] -> Tree a -> Tree (label,a)
bf_label ls = head . bf_zip . bfz_label ls . bf_unzip . (:[])
tree1l = bf_label [101..] tree1
{-
Node (101,1)
(Node (102,2) (Leaf (104,3))
(Node (105,4) (Leaf (108,5))
(Leaf (109,6))))
(Node (103,12) (Node (106,14) (Leaf (110,15))
(Leaf (111,16)))
(Leaf (107,13)))
-}
-- A sample tree
tree2 = Node 1 (Node 2 (Leaf 3)
(Node 4 (Leaf 5)
((Node 6) (Leaf 18)
(Leaf 19))))
(Node 12 (Node 14 (Leaf 15)
(Leaf 16))
(Leaf 13))
tree2l = bf_label [101..] tree2
*