haskell - 追踪一棵树？

Question

我有一个像这样的树的类型:

data Tree a = EmptyTree | Tree a [Tree a] deriving (Show, Ord, Eq)

freeTree :: Tree Integer  
freeTree =  Tree 2 [Tree 5 [], Tree 6 [Tree 8 [], Tree 9 []], Tree 7 []]

main = print freeTree

我想做的是编写一个可以这样使用的函数:

trace freeTree

这棵树上的跟踪将返回: [2],[2,5],[2,6],[2,7],[2,6,8],[2,6,9]
基本上它的作用是:

保留一个已经在“堆栈”上的节点列表(每个深度的根节点将我们带到这里)。每次到达新节点时，将堆栈节点列表++ current_node 的列表添加到结果列表中。

任何人都可以就如何做到这一点提供任何建议吗？

谢谢

Answer 1

第一个(不是真正有效的实现):

trace :: Tree a -> [[a]]
trace t = trace' [([],t)] []

type Level a = [([a],Tree a)]

trace' :: Level a -> Level a -> [[a]]
trace' [] [] = []                                         -- current and next level empty? We're done!
trace' [] l = trace' l []                                 -- current level exhausted? Next level becomes current level and we construct a new level
trace' ((_,EmptyTree):ts) lu = trace' ts lu               -- currently an EmptyTree? Skip it
trace' ((h,Tree t c):ts) lu = ht : trace' ts (lu++el)     -- currently a tree? Enumerate and add childs
    where ht = h++[t]
          el = map (\x -> (ht,x)) c

该算法使用两个 Level a的，当前级别和下一个级别。您总是首先迭代当前级别，并且对于当前级别中的每个项目，将该级别的子项添加到下一个级别，直到当前级别用尽。这种方法的唯一问题是 ++操作非常昂贵，特别是因为它们是应用左关联而不是右关联。通过使用更紧凑的元组列表表示，还可以使其内存效率更高。

您可以使用 来提高效率。先进先出队列 ，例如 this one (让我们假设至少所有队列的接口(interface)都是相同的，所以如果您更喜欢另一个，您可以交换位置)。

在这种情况下，代码将显示为:

type Level a = [([a],Tree a)]
type LevelFiF a = FIFO ([a],Tree a)

trace' :: Level a -> LevelFiF a -> [[a]]
trace' [] ln | isEmpty ln = []
             | otherwise = trace' (toList ln) empty
trace' ((h,Tree t c):ts) ln = ht : trace' ts (foldl (flip enqueue) ln el)
    where ht = h++[t]
          el = map (\x -> (ht,x)) c
trace' (_:ts) ln = ht : trace' ts ln

您也可以使用 Haskell 的单子(monad)队列之一来提高效率。