Haskell: 扁平化二叉树

Question

我在考虑将二叉树展平为一个列表，以便进行后续处理。

我最初想到使用 (++) 将左右分支连接起来，但是后来想到在最坏情况下这将花费 O(n^2) 的时间。

然后我想到倒序构建列表，在常数时间内使用 (:) 在前面附加。然而，我又想如果我将此列表发送给类似于fold的函数，则必须等待整个树被遍历后才能开始折叠，因此无法使用列表融合。

然后我想出了以下方法：

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) 的时间内运行，使用的"堆栈空间"不会超过树的最大深度，而且能否与消耗函数合并（即中间列表被消除）？这是展开树的"正确"方法吗？

- Clinton

---

http://hackage.haskell.org/packages/archive/containers/latest/doc/html/src/Data-Map-Base.html#foldl - Thomas M. DuBuisson

正如luqui所指出的那样，这是一种差异列表技术。这个和这个也是相关的。 - Will Ness

Answer 1

我对合并不了解，但我认为一般递归函数无法被合并。但是请记住，在Haskell中处理列表时，中间列表通常不会作为一个整体存在——您将知道开头而没有计算结尾，然后稍后您将抛弃开头并知道结尾（在列表元素数量的步骤中）。这不是合并，这更像是"流的良好行为"，意味着如果按增量消耗输出，则空间要求更好。

无论如何，是的，我认为这是扁平化树的最佳方法。当算法的输出是列表但列表未被检查，且存在连接操作时，差异列表（DList）通常是最佳选择。它们将列表表示为"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是以高效的方式完成此操作的规范方式，这就是你所做的。

- luqui

---

为了更深入地探讨DLists的理论方面，Haskell维基上有一篇关于DLists的文章（诚然不是很清晰），但基本思想是避免通过O(n)嵌套应用程序(++)来获取第一个元素，而是可以直接从最外层函数（最左边的(.)应用）中获取它。（注意：这是一个广泛的总结，实际情况比这个略微复杂。） - huon

Answer 2

flatten'是尾递归的，因此不应该占用任何堆栈空间。但它会沿着树的左侧向下走，在堆中产生一堆thunks。如果您在示例树上调用它并将其减少到WHNF，则应该得到类似于以下内容的东西：

  :
 / \
1  flatten' Tip :
               / \
              2   flatten' (Node 4) []
                           /      \
                         (Node 3) Tip
                        /       \
                       Tip      Tip

该算法的时间复杂度为O(N)，但它必须检查Tip和Node。

这似乎是按顺序展平树的最有效方法。 Data.Tree模块有一个flatten函数在这里，它做了类似的事情，只是它更喜欢先序遍历。 更新： 在图形缩减引擎中，main中的flatten将生成以下图形：

               @
              / \
             @  []
            / \
           /   \
          /     \
       flatten' Node 2
                /    \
               /      \
              /        \
           Node 1    Node 4
           /   \     /   \
          Tip  Tip  /     \
                   /       \
                Node 3     Tip
                /   \
               Tip  Tip

为了将其减少至WHNF，图形缩减引擎将展开脊柱，将[]和Node 2推入堆栈。然后它将调用flatten'函数，该函数将重写图形为：

                 @
                / \
               /   \
              /     \
             @       :
            / \     / \
           /   \   2   \
          /     \       \
       flatten' Node 1   \
                /   \     \
               Tip  Tip    @
                          / \
                         @  []
                        / \
                       /   \
                      /     \
                   flatten' Node 4
                            /   \
                           /     \
                          /       \
                       Node 3     Tip
                       /   \
                      Tip  Tip

将从栈中弹出两个参数。根节点仍未处于 WHNF 状态，因此图形缩减引擎将展开脊柱，将 2:... 和 Node 1 推入栈中。然后它将调用 flatten' 函数，该函数将重写图形为：

                 @
                / \
               /   \
              /     \
             @       :
            / \     / \
           /   \   1   \
          /     \       \
       flatten' Tip      @
                        / \
                       /   \
                      /     :
                     @     / \
                    / \   2   \
                   /  Tip      @
                  /           / \
               flatten'      @  []
                            / \
                           /   \
                          /     \
                       flatten' Node 4
                                /   \
                               /     \
                              /       \
                           Node 3     Tip
                           /   \
                          Tip  Tip

将从堆栈中弹出两个参数。根节点仍未进入WHNF，因此图形缩减引擎将展开脊柱，将1:...和Tip推入堆栈。然后它将调用flatten'函数，该函数将重写图形为：

                 :
                / \
               1   \
                    \
                     @
                    / \
                   /   \
                  /     :
                 @     / \
                / \   2   \
               /  Tip      @
              /           / \
           flatten'      @  []
                        / \
                       /   \
                      /     \
                   flatten' Node 4
                            /   \
                           /     \
                          /       \
                       Node 3     Tip
                       /   \
                      Tip  Tip

并将从堆栈中弹出两个参数。我们现在处于 WHNF 状态，最多使用了两个堆栈条目（假设 Tree 节点不是需要额外堆栈空间来评估的惰性求值）。

因此，flatten' 是尾递归的。它可以替换自身，而无需评估其他嵌套的 redexes。第二个 flatten' 仍然是一个位于堆上的 thunk，而不是位于堆栈上。

- pat

---

flatten 不是尾递归。有两个递归调用。 - newacct