how to use traversable on a tree

Question

I'm trying to understand how I can use Traversable to iterate over my tree data structure. I've got this ugly tree (forest actually) that looks like this:

data ParseTree a = Leaf a | Node a (ParseTree a) (ParseTree a) | MultiNode a [ParseTree a]
       deriving (Show, Functor, F.Foldable, T.Traversable)

t = Node S 
(Node NP (Leaf DP) (Leaf NP)) 
(MultiNode VP 
[Node VP (Node VP (Leaf VP) (Leaf PP)) (Node NP (Leaf DP) (Leaf NP)),
Node VP (Leaf VP) (Node PP (Leaf PP) (Node NP (Leaf DP) (Leaf NP)))]
)

I want to find the multinodes so I can replace build new trees, one for each item in the multinode.

its easy enough for me to write a function like this

findmulti :: ParseTree a -> [ParseTree a]
findmulti (Leaf a) = []
findmulti (Node a left right) = findmulti left ++ findmulti right
findmulti (MultiNode a lst) = [ (MultiNode a lst) ]

But I think I should be able to use traverse to go down the list and find the items for me. if I do

traverse print t

I get only the values at the very end:

S NP DP NP VP VP VP VP PP...

But I actually want the traversal to stop at the Multinodes. How do I control the depth of the traversal? Or is that not possible because Traversable and friends are agnostic as to the container?

Eventually I want to derive lenses that will allow me to replace the multinodes too, but right now I'm just trying to get a grasp on how traversable works. Am I even using the right tool for the job?

Answer 1

It's fairly easy to build a Traversal' which visits whatever you like, though this capability is much more general than what Data.Traversable allows as that Traversal must visit only and exactly the contained elements.

To begin, let's examine the signature of traverse

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

I like to call the first argument the "injection" function. Anything that is injected into the Applicative, f, is "visited" by the Traversal. In this case, we'd like to visit the MultiNodes so we can specialize this type already.

multinodes :: Applicative f => (ParseTree a -> f (ParseTree a)) -> ParseTree a -> (f (ParseTree a))

Or

multinodes :: Traversal' (ParseTree a) (ParseTree a)

Now let's consider the definition. Again, the goal is to inject each MultiNode.

-- No multinodes here, so we use `pure` so as to inject nothing at all
multinodes inj l@Leaf{} = pure l

-- Here's a multinode, so we'll visit it with the injection function
multinodes inj m@Multinode{} = inj m

-- And we need to neither reject (thus stopping the traversal)
-- nor inject a branch. Instead, we continue the traversal deeper
multinodes inj (Node a l r) = 
  (\l' r' -> Node a l' r') <$> multinodes inj l
                             <*> multinodes inj r

This is our Traversal'.

>>> t ^.. multinodes
[MultiNode VP [Node VP (Node VP (Leaf VP) (Leaf PP)) (Node NP (Leaf DP) (Leaf NP)),Node VP (Leaf VP) (Node PP (Leaf PP) (Node NP (Leaf DP) (Leaf NP)))]]

---

This code isn't much shorter than the code written for findmulti---in fact, it's nothing more than an unfolded findMulti . traverse, but it's immediately compatible with other lens combinators and demonstrates the general method of feeding an Applicative through a type while targeting the desired inner structures. Writing this Traversal' just once will be a general tool for almost any kind of visitation upon the MultiNodes.