How to find path to a node in a Haskell Data.Tree
haskell, tree
Solution
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.
Problem
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?