Haskell:拼合二叉树

Question

我正在考虑将二进制树展平为列表,以便进行后续处理.

我首先考虑使用(++)加入左右分支,但后来想到了更糟糕的情况需要O(n^2)时间.

然后我考虑向后构建列表,使用(:)在线性时间附加到前面.然而,我想如果我将这个列表发送到类似折叠的函数,它必须等到整个树遍历才能开始折叠,因此不能使用列表融合.

然后我想出了以下内容:

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中处理列表时,中间列表通常不会同时存在 - 你会知道开头并且没有计算结束,然后你会抛弃开头并知道结束(与列表中的元素一样多的步骤).这不是融合,这更像是"流良好行为",并且意味着如果输出逐渐消耗,则空间要求更好.

无论如何,是的,我认为这是压扁树的最佳方式.当一个算法的输出是一个列表,但否则列表是浑浑噩噩,并有串联回事,那么差异列表(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 []

这些是实现的基本要素,其余的可以从中得出.DLists中的朴素平坦化算法是:

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是有效地做到这一点的规范方法,这就是你所做的.