从“树路径”列表中构建森林

Question

从“树路径”列表开始，例如：

[["a", "b", "c"], ["a", "b", "e"], ["f", "g"]]

我想建造一片森林(

[Tree]

):

a
|_ b
  |_ c
  |_ e
f
|_ g

这是我迄今为止的尝试。我一直在构建构建块以组装最终的解决方案：

module Main where

import Data.Tree

insertPath :: Eq a => [a] -> [Tree a] -> [Tree a]
insertPath [] ts = ts
insertPath (y:ys) [] = Node y [] : []
insertPath (y:ys) ((Node x ts):ts')
    | y /= x = Node x ts : insertPath ys ts'
    | otherwise = Node x (insertSubTrees ys ts) : insertPath ys ts'

insertSubTrees :: Eq a => [a] -> [Tree a] -> [Tree a]
insertSubTrees [] ts = ts
insertSubTrees (y:ys) [] = insertSubTrees ys [Node y []]
insertSubTrees (y:ys) (t:ts) = undefined

我的问题是：

• 我应该在

  Tree

  或

  Tree

  列表上定义函数吗？
• 我的方法合理吗？还有什么其他选择？
• 如何开发

  buildForest :: Eq a => [a] -> [Tree a] -> [Tree a]

  功能？

Answer 1

我认为你把事情变得过于复杂了：如果你到达了路径的尽头，我们就完成了。所以我们可以在一个函数中做到这一点：

insertPath :: Eq a => [a] -> [树 a] -> [树 a]
插入路径[] = id
insertPath (p : ps) = go
  在哪里
    go[]=[节点p(insertPath ps[])]
    go (n@(节点 x xs) : ns)
      | p == x = 节点 x (insertPath ps xs) : ns
      |否则 = n : 继续 ns

然后您可以使用路径列表生成整个森林：

insertPaths :: Eq a => [树 a] -> [[a]] -> [树 a]
insertPaths = Foldl (翻转 insertPath)

使用样本数据，我们生成一个森林：

ghci> insertPaths [] [["a", "b", "c"], ["a", "b", "e"], ["f", "g"]]
[Node {rootLabel = "a", subForest = [Node {rootLabel = "b", subForest = [Node {rootLabel = "c", subForest = []},Node {rootLabel = "e", subForest = []}]}]},Node {rootLabel = "f", subForest = [Node {rootLabel = "g", subForest = []}]}]