algorithm - Haskell:展平二叉树

Question

我正在考虑将二叉树展平为列表，以供后续处理。

我首先想到使用 (++) 连接左右分支，但后来想到在更坏的情况下需要 O(n^2)时间。

然后我想到向后构建列表，使用 (:) 在线性时间内追加到前面。但是，然后我想如果我将这个列表发送到类似折叠的函数，它必须等到整个树被遍历才能开始折叠，因此不能使用 list fusion。 .

然后我想出了 following :

data Tree a = Node a (Tree a) (Tree a) | Tip

flatten :: Tree a -> [a]
flatten x = (flatten' x) []

flatten' :: Tree a -> [a] -> [a]
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
flatten' Tip l = l

main = 
  putStrLn $ show $ flatten $ 
    (Node 2 (Node 1 Tip Tip) (Node 4 (Node 3 Tip Tip) Tip))

这会在 O(n) 时间内工作吗，占用“堆栈空间”不超过与树的最大深度成正比，并且它可以与消耗函数融合(即消除中间列表)?这是压扁树的“正确”方法吗？

Answer 1

我不太了解融合，但我认为一般的递归函数不能融合。但是请记住，当你在 Haskell 中处理列表时，中间列表通常不会作为一个整体同时存在——你会知道开始但没有计算结束，然后你会丢掉开始并知道最后(在与列表元素一样多的步骤中)。这不是融合，这更像是“stream well-behavedness”，意味着如果输出是增量消耗的，空间需求会更好。

无论如何，是的，我认为这是压扁一棵树的最好方法。当算法的输出是一个列表，但列表未经检查，并且正在进行串联时，则 difference lists (DLists) 通常是最好的方式。它们将列表表示为“prepender 函数”，这消除了追加时遍历的需要，因为追加只是函数组合。

type DList a = [a] -> [a]

fromList :: [a] -> DList a
fromList xs = \l -> xs ++ l

append :: DList a -> DList a -> DList a
append xs ys = xs . ys

toList :: DList a -> [a]
toList xs = xs []

这些是实现的要点，其余的可以从中推导出来。 DList 中的朴素展平算法是:

flatten :: Tree a -> DList a
flatten (Node x left right) = flatten left `append` fromList [x] `append` flatten right
flatten Tip = fromList []

让我们做一点扩展。从第二个等式开始:

flatten Tip = fromList []
            = \l -> [] ++ l
            = \l -> l
flatten Tip l = l

看看这是怎么回事？现在是第一个等式:

flatten (Node x left right) 
    = flatten left `append` fromList [x] `append` flatten right
    = flatten left . fromList [x] . flatten right
    = flatten left . (\l -> [x] ++ l) . flatten right
    = flatten left . (x:) . flatten right
flatten (Node x) left right l
    = (flatten left . (x:) . flatten right) l
    = flatten left ((x:) (flatten right l))
    = flatten left (x : flatten right l)

这表明 DList 公式如何等于您的函数!

flatten' :: Tree a -> [a] -> [a]
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
flatten' Tip l = l

我没有任何证据证明为什么 DList 比其他方法更好(最终这取决于您如何使用输出)，但是 DList 是有效地执行此操作的规范方法，这就是您所做的。