How to find path to a node in a Haskell Data.Tree

Question

Given a tree in Haskell (represented by a Data.Tree), how could I find the path to a node?

e.g.

import Data.Tree

tree = Node 1 [Node 2 [Node 3 []], Node 4 []]

Which forms a tree that looks like:

1
|
+- 2
|  |
|  `- 3
|
`- 4

How could I make a function pathToNode such that:

pathToNode 0 tree => []
pathToNode 1 tree => [1]
pathToNode 2 tree => [1, 2]
pathToNode 3 tree => [1, 2, 3]
pathToNode 4 tree => [1, 4]

In my particular case, any given value will appear only once in the tree, so a solution that returns the a path to a value is acceptable.

So far my best answer is this:

pathToNode :: (Eq a) => a -> Tree a -> [a]
pathToNode x (Node y ys) | x == y    = [x]
                         | otherwise = case concatMap (pathToNode x) ys of
                                         [] -> []
                                         path -> y:path

Is there a more succinct way of writing this? Is it possible to take advantage of Data.Foldable or Data.Traversable to avoid writing my own traverse logic?

Answer 1

The default Traversable and Foldable instances can't be used here, since they don't provide enough contextual information to maintain a path (e. g. when traversing in the State monad). They both visit each element of the tree once in some order, so you can't know whether some previously visited value belongs to a parent or sibling node of the current node.

I think the following function is succinct enough:

pathsToNode :: Eq a => a -> Tree a -> [[a]]
pathsToNode x (Node y ns) = [[x] | x == y] ++ map (y:) (pathsToNode x =<< ns)

It lists the paths to all copies of x, but you can always just lazily take the first found path if that's what you want.