具有边缘信息的Haskell树

Question

Haskell库中是否存在这种数据结构？我做了一些搜索，但找不到任何有用的东西。我想使用现有的类型，而不是定义我自己的类型——它似乎应该存在。

data MyTree e n = Node { rootLabel :: n
                       , subForest :: Map e (MyTree e n)
                       }

这个想法是它与Data. Tree非常相似，但是边可以保存信息和节点。

如果你有一个通过树的路径（类型为[e]），你可以在O（log（n））中找到rootLabel（类型为n）。据我所知，你不能用Data做这件事。树，因为您必须扫描每个节点的子节点，以查找路径前进到的节点。这是因为数据的类型。树的子森林是[树a]。

特别是，我对公开具有类似于以下类型的函数的实现感兴趣：

getNextLevel :: e -> MyTree e n -> MyTree e n

这将在树中更深地潜入一层，给定一个可以遍历的边缘。

Answer 1

您可以始终使用图形库，并确保将其保存为一棵树。

Answer 2

这种数据类型看起来很像trie树，Hackage上有很多包可以使用。