haskell - 如何在 Haskell Data.Tree 中找到节点的路径

Question

给定 Haskell 中的一棵树(由 Data.Tree 表示)，我如何找到节点的路径？

例如

import Data.Tree

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

这形成了一棵树，看起来像:

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

我怎么能做一个函数 pathToNode使得:

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

在我的特定情况下，任何给定的值在树中只会出现一次，因此可以接受返回值的路径的解决方案。

到目前为止，我最好的答案是:

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

有没有更简洁的写法？是否可以利用 Data.Foldable或 Data.Traversable避免编写自己的遍历逻辑？

Answer 1

默认Traversable和 Foldable实例不能在这里使用，因为它们没有提供足够的上下文信息来维护路径(例如，在 State monad 中遍历时)。它们都以某种顺序访问树的每个元素一次，因此您无法知道某些先前访问过的值是否属于当前节点的父节点或兄弟节点。

我认为以下功能足够简洁:

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

它列出了 x 的所有副本的路径，但如果这是你想要的，你总是可以懒惰地选择第一个找到的路径。