Traversing a rose tree with Data.Tree.Zipper

Question

I have a rose tree structure that I'm representing with Data.Tree. Each node in the tree is labeled with an (x,y) coordinate. I need to implement a way of finding the node in the tree that is nearest to a given query coordinate and adding a child to that node.

I envision dividing this into two operations:

1. traverse the tree to find the node that is nearest to a given query coordinate

2. take the node found in the prior traversal and add to it a child labeled with the above query coordinate

The only way I can think of doing this is to traverse the tree in step 1 using Data.Tree.Zipper, and then using that zipper in step 2 to insert a node in a specific location.

I have two questions:

• Is this an effective way to approach the problem?

• If so, how do I use the functions in Data.Tree.Zipper to implement step 1 above? I'm finding the tree traversal difficult to implement because it requires recursion in two dimensions: depth and breadth.

Answer 1

You don't need zippers to do simple tree traversals.

import Data.Foldable (minimumBy)
import Data.Function (on)
import Data.Tree

addPt :: (Eq a, Ord b) => (a -> a -> b) -> a -> Tree a -> Tree a
addPt dist p t = down t
  where
    down (Node a xs)
      | a == closest = Node a (Node p []:xs)
      | otherwise    = Node a (map down xs)
    closest = minimumBy (compare `on` dist p) t

This will add the point multiple times if the closest point as returned by minimumBy is duplicated, and could be made slightly more efficient since down always traverses the tree fully, even if it finds the element early. To fix both issues, you could write a function that explores each branch in turn, returning the (possibly augmented) branch plus, say, a Bool to indicate whether the point was added. On the other hand, addPt is naturally highly parallelizable (modulo the use of linked lists in Data.Tree, and replacing minimumBy by a parallel version) and this is lost if you try to save work by sequentializing it. Using a zipper could certainly be somewhat more efficient in the sequential case.

Answer 2

Here's how you can implement step 1 without assuming anything about the layout of a tree. For simplicity, I'm going to pick out the minimal node, rather than the node that minimizes some function, but it's not hard to modify this idea. For some reason, rosezipper doesn't offer an operation to get all the children of a zipper, so we have to implement that first. Once we've done that, the idea is pretty simple: recurse on the children, then pick the minimum of either the current location or the results of the recursion.

import Data.List
import Data.Ord
import Data.Tree
import Data.Tree.Zipper

childrenAsList :: TreePos Full a -> [TreePos Full a]
childrenAsList = go . children where
    go z = case nextTree z of
        Nothing -> []
        Just z  -> z : go (nextSpace z)

minZipper :: Ord a => Tree a -> TreePos Full a
minZipper = go . fromTree where
    go z = minimumBy (comparing (rootLabel . tree))
                     (z:map go (childrenAsList z))

You certainly don't need to use a zipper to do something efficient, but it is certainly one reasonable and good way to approach the problem. One advantage of this approach compared to the two-traversal approach is that it should have maximal sharing.