One of the solutions that did not make it into my yield paper (though I sort of liked it) was one that used “braiding”.
The problem here is to do a breadth first traversal of a binary tree. I was looking for a solution using my pet control operator yield. The braiding solution occurred to some months back as a consequence. The solution that finally made it into the paper was one based on a more traditional queue based breadth first traversal (BFT from now on) which did have better perf than the braiding solution. I am however documenting the braiding solution here because I think its elegant at some level.
So how would one do a BFT of a binary tree? Look at this entry for a slightly more detailed problem description. Simple, we start out by defining braiding.
Say you have two yield based iterators. These are just computations that yield values during their process of evaluation. These iterators yield values of type Maybe. For those unfamiliar with the Haskell type “Maybe”, here is a definition –
data Maybe a = Just a | Nothing
It simply says that a value of type maybe is either some actual value or the special value nothing. If you desperately need an analog, think of it as a pointer or a reference – it either points to some object or its null.
So a stream of maybe-values looks like this
x1 x2 # x3 x4 x5 # # x6 # ..
where the ‘x’ denote actual values and the # denotes occasional ‘Nothing’. If one had two such streams of values, then one can braid them as follows. Consider the stream of xs’ and the stream of ys.
x1 x2 # x3 x4 x5 # # x6 # ..
y1 # y2 y3 # y4 y5 # y6 y7 # ..
On braiding gives a single stream with that switches between the original streams every time it sees a Nothing. This results is a single stream like this –
x1 x2 y1 # x3 x4 x5 y2 y3 # y4 y5 # x6 y6 y7 # ..
This is how braiding works.
So how does one do a BFT? Simple, one recursively traverses the tree as follows –
- If you are at a leaf, yield the leaf value and then yield a Nothing.
- If you are at a branch, yield the branch value, a Nothing and then braid the iterators of the left and right branches.
Simple – that’s a breadth first traversal. If you look at the algorithm closely you will realize that final stream produced will be in the breadth first order but will also contain occasional Nothing values – the Nothing values will be precisely in the those places when values of one level deeper in the tree are being produced. (Of course, you don’t want to expose the Nothings you can add a filter and remove them).
The other important observation, which is also a requirement of the problem, is that the values used to resume the iterator will be available to the branches or leafs that yielded the corresponding value – hence tree reconstruction is trivial.
-- This a breadth first tree walk that reconstructs the tree from the
-- the return values of the yield. It is expands the tree one level at
-- a time and internally uses Nothing to communicate level changes.
bfTreeWalk :: Tree a -> Yield i a (Tree i)
bfTreeWalk tr = suppressMaybe $ bft tr
where
bft (L v) = do (Just v') <- yield (Just v);
yield Nothing;
return (L v')
bft (B v t1 t2) = do (Just v') <- yield (Just v);
yield Nothing;
(t1',t2') <- braidMaybe (bft t1)(bft t2);
return (B v' t1' t2')
Here is the tree walk in Haskell. Even if you are not able to run or fully grok the Haskell code above, you should be able to use it as a guide to reconstruct the solution in your pet language.
The supporting braid and suppress functions are below –
-- Convert maybe values into real values by ignoring the Nothing.
-- 1 2 10 # 3 30 # 5 6 70 50 # 8 ...
-- Becomes
-- 1 2 10 3 30 5 6 70 50 8 ...
suppressMaybe :: Yield (Maybe i) (Maybe o) r -> Yield i o r
suppressMaybe yb = runMapY yb sM
where
sM Nothing = return Nothing
sM (Just v) = do r <- yield v;
return (Just r)
-- Alternates two iterators, every time one yields a Nothing
-- 1 2 # 3 # 5 6 # 8 ....
-- 10 # 30 # 70 50 # 80 ....
-- and makes (where # is a Nothing)
-- 1 2 10 # 3 30 # 5 6 70 50 # 8 .. 80 ... ....
braidMaybe :: Yield (Maybe i) (Maybe o) r -> Yield (Maybe i) (Maybe o) r -> Yield (Maybe i) (Maybe o) (r, r)
braidMaybe yb1 yb2 = bM (runYield yb1) (runYield yb2) True
where
bM (Iterator (Just v) k) it ord = do i <- yield (Just v); bM (k i) it ord
bM it1 it2 False = do yield Nothing; bM it2 (resume it1) True
bM (Iterator Nothing k) it True = bM it (k Nothing) False
bM (Done v1) (Done v2) True = return (v1, v2)
bM (Done v) it True = bM it (Done v) False
resume (Iterator Nothing k) = (k Nothing)
resume it = it
The code above uses a monadic yield implementation and can as easily be expressed by any language which supports a good yield operator. (As of now I have a yield implementation for Haskell and Scheme and I believe Sid has ones for Python and Ruby (?))
At this point I should note that I was referred to the naïve implementation of BFT using nested lists by Simon Peyton Jones. The cods is below
breadthFirstTW :: Tree Int -> [Int]
breadthFirstTW t = concat (bft t)
where
bft :: Tree a -> [[a]]
bft (L x) = [[x]]
bft (B t1 t2) = b_zip (bft t1) (bft t2)
b_zip :: [[a]] -> [[a]] -> [[a]]
b_zip [] ys = ys
b_zip xs [] = xs
b_zip (x:xs) (y:ys) = (x++y) : (b_zip xs ys)
The essential idea behind the braiding traversal is not very different from that of the nested solution with the operational encoding of nested lists using Maybe. However looking at the nested list solution, at this point, it is not apparent to me how it can be extended to reconstruct the tree.
The implementation of the monadic yield that this relies on is documented in my paper which I hope to put up on my academic website soon enough.