0

我正在使用以下类型的树版本：

Tree = Empty | Leaf Event | Split String [(String, Tree)]

我的目标是获得一个函数，该函数返回一个对列表，[(Event,[Int])]其中[Int]包含每个事件的坐标（在树中到达它的路径），即如果树是：

Split str [(str2, Leaf event), (str3, Empty)]

然后我希望它返回[event,[0]]。我想忽略树的任何空头。

所以我的功能看起来像

coords :: Tree -> [(Event,[Int])]
coords Empty = []
coords (Leaf event) = [event, []]

然后对于拆分它需要递归地在每个子树上应用该函数。我想过这样做：

coords Split str xs = zip (coords trees) [1..] where
    trees = [snd(str,tree) | (str,tree) <-xs]

但这会给我提供任意长度的嵌套列表，以及其他几个问题。有任何想法吗？

4

1 回答 1

2

一个可能的解决方案可能是：

coords (Split _ xs) = [ (event, n:path)
      | (n,(_,tree)) <- zip [1..] xs 
      , (event, path) <- coords tree  ]

xs这首先使用zip [1..]OP 中的方法来枚举 中的树。我们得到了一种三元组的列表(n,(string,tree))，我们不需要string. 对于任何这样的“三元组”，我们使用 进行递归coords tree：这会生成一个表单列表，[(event1, path1), (event2, path2), ...]其中路径相对于tree，而不是相对于Split str xs。我们需要n在每条路径前面添加，所以我们最终生成(event, n:path).

于 2018-03-20T13:18:08.577 回答