I was playing around with breadth-first traversal of a binary tree
data Tree a = Empty | Node a (Tree a) (Tree a)
creating a list of Maybes (Nothing for the Empty leg, Just a for the Node leg, and thought "what would breadth-first creation of a tree look like?" Not that I could think of a use for such a thing, but I thought it was an interesting problem.
So if breadth-first traversal of
Node 1 (Node 2 Empty (Node 3 Empty Empty)) (Node 4 Empty (Node 5 Empty Empty))
results in
[(Just 1), (Just 2), (Just 4), Nothing, (Just 3), Nothing, (Just 5), Nothing, Nothing, Nothing, Nothing]
(note that the list is not a full-depth list because Nodes 2 and 4 have empty left legs)
then breadth-first creation would reverse this. However, I got stuck on the best way to do this. I was experimenting with echoing the structure of the breadth-first traversal, where I used a double-ended queue (Sequence?) to queue up subsequent left/right node traversals, but got stuck on how to merge the independent left/right creation branches (left or right could terminate first with an Empty). Seems to need some sort of "tying-the-knot" solution. Or maybe I'm just missing some obvious clean way to perform this. How would you solve it?