14

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

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

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

然后我想出了以下内容：

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)及时工作，占用的“堆栈空间”不超过树的最大深度，并且可以与消耗函数融合（即消除中间列表）？这是压平树的“正确”方法吗？

4

2 回答 2

12

我对融合了解不多，但我认为递归函数一般不能融合。但是请记住，当您在 Haskell 中处理列表时，中间列表通常不会同时作为一个整体存在——您将知道开始而不计算结束，然后您将丢弃开始并知道结束（在与列表元素一样多的步骤中）。这不是融合，这更像是“流的良好行为”，意味着如果增量消耗输出，空间需求会更好。

无论如何，是的，我认为这是压平一棵树的最佳方法。当算法的输出是一个列表，但该列表未经检查，并且正在进行连接时，差异列表（DLists）通常是最好的方法。它们将列表表示为“前置函数”，这消除了追加时遍历的需要，因为追加只是函数组合。 

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 []

这些是实现的要领，其余的可以从中派生。s 中的朴素扁平化算法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是有效地做到这一点的规范方法，这就是你所做的。

于 2012-05-15T04:32:02.820 回答
2

flatten'是尾递归的，所以它不应该占用任何堆栈空间。然而，它会沿着树的左侧向下走，在堆中吐出一堆 thunk。如果您在示例树上调用它，并将其简化为 WHNF，您应该得到如下所示的内容：

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

该算法是O(N)，但它必须检查Tips 以及Nodes。

这看起来是按顺序展平树的最有效方法。该Data.Tree模块在这里flatten有一个函数，它做很多相同的事情，除了它更喜欢前序遍历。

更新：

在图形缩减引擎中，flatteninmain将生成如下图：

               @
              / \
             @  []
            / \
           /   \
          /     \
       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节点不是需要额外堆栈空间来评估的 thunk）。

所以，flatten' 是尾递归的。它无需评估额外的嵌套 redexes 即可替换自身。第二个flatten'仍然是堆中的一个 thunk，而不是堆栈。

于 2012-05-15T04:40:27.983 回答