是否可以通过O(1)内存使用延迟遍历递归数据结构,尾部调用优化？

Question

假设我们有一个递归数据结构,就像二叉树一样.有许多方法可以遍历它,它们具有不同的内存使用配置文件.例如,如果我们只是打印每个节点的值,使用伪代码,如下面的按顺序遍历...

visitNode(node) {
    if (node == null) return;
    visitNode(node.leftChild);
    print(node.value);
    visitNode(node.rightChild);
}

...我们的内存使用量是常量,但由于递归调用,我们会增加调用堆栈的大小.在非常大的树上,这可能会溢出它.

假设我们决定针对调用堆栈大小进行优化; 假设这种语言能够进行适当的尾调,我们可以将其重写为以下预先遍历...

visitNode(node, nodes = []) {
    if (node != null) {
        print(node.value);
        visitNode(nodes.head, nodes.tail + [node.left, node.right]);
    } else if (node == null && nodes.length != 0 ) {
        visitNode(nodes.head, nodes.tail);
    } else return;
}

虽然我们永远不会破坏堆栈,但我们现在看到堆使用量相对于树的大小线性增加.

假设我们当时试图懒洋洋地遍历树 - 这就是我的推理变得模糊的地方.我认为即使使用基本的懒惰评估策略,我们也会以与尾部优化版本相同的速度增长内存.下面是使用Scala的Stream类的具体示例,它提供了延迟评估:

sealed abstract class Node[A] {
  def toStream: Stream[Node[A]]
  def value: A
}

case class Fork[A](value: A, left: Node[A], right: Node[A]) extends Node[A] {
  def toStream: Stream[Node[A]] = this #:: left.toStream.append(right.toStream)
}

case class Leaf[A](value: A) extends Node[A] {
  def toStream: Stream[Node[A]] = this #:: Stream.empty
}

虽然只对流的头部进行严格评估,但无论何时left.toStream.append(right.toStream)进行评估,我认为这实际上会评估左右两个流的头部.即使它没有(由于追加聪明),我认为以递归方式构建这个thunk(从Haskell借用一个术语)本质上会以相同的速率增长内存.我不是说"将这个节点放在要遍历的节点列表中",而是基本上说,"这是评估的另一个值,它会告诉你下一步要穿什么",但结果是一样的; 线性记忆增长.

我能想到的唯一策略是避免这种情况,即每个节点都有可变状态,声明已经遍历了哪些路径.这将允许我们有一个引用透明的函数,它说:"给定一个节点,我将告诉你下一个应该遍历的单个节点",我们可以用它来构建一个O(1)迭代器.

有没有另一种方法可以实现O(1),二进制树的尾调优化遍历,可能没有可变状态？

Answer 1

有没有另一种方法可以实现O(1),二进制树的尾调优化遍历,可能没有可变状态？

正如我在评论中所述,如果树不需要在遍历中存活,您就可以这样做.这是一个Haskell示例:

data T = Leaf | Node T Int T

inOrder :: T -> [Int]
inOrder Leaf                     =  []
inOrder (Node Leaf x r)          =  x : inOrder r
inOrder (Node (Node l x m) y r)  =  inOrder $ Node l x (Node m y r)

如果我们假设垃圾收集器将清理Node我们刚处理的任何东西,那么这需要O(1)辅助空间,因此我们有效地用右旋转版本替换它.但是,如果我们处理的节点不能立即被垃圾收集,那么final子句可能会在它到达叶子之前建立O(n)个节点数.

如果你有父指针,那么它也是可行的.但是,父指针需要可变状态,并且防止共享子树,因此它们实际上不起作用.如果您通过(cur, prev)最初的一对表示迭代器(root, nil),那么您可以执行此处概述的迭代.但是,您需要一种带指针比较的语言才能使其工作.

如果没有父指针和可变状态,您需要维护一些数据结构,至少跟踪树根的位置以及如何到达那里,因为在顺序或后序中的某个时刻您需要这样的结构遍历.这种结构必然需要Ω(d)空间,其中d是树的深度.

Answer 2

一个奇特的答案.

我们可以使用免费的monad来获得有效的内存利用率限制.

    {-# LANGUAGE RankNTypes
               , MultiParamTypeClasses
               , FlexibleInstances
               , UndecidableInstances #-}

    class Algebra f x where
      phi :: f x -> x

一个仿函数的代数f是一个函数phi从f x到x一些x.例如,任何monad都有任何对象的代数m x:

    instance (Monad m) => Algebra m (m x) where
      phi = join

f可以构造任何仿函数的免费monad (可能只有某种类型的仿函数,比如omega-cocomplete,或者其他类似的;但是所有Haskell类型都是多项式仿函数,它们都是omega-cocomplete,因此对所有Haskell来说肯定都是正确的函子):

    data Free f a = Free (forall x. Algebra f x => (a -> x) -> x)
    runFree g (Free m) = m g

    instance Functor (Free f) where
      fmap f m = Free $ \g -> runFree (g . f) m

    wrap :: (Functor f) => f (Free f a) -> Free f a
    wrap f = Free $ \g -> phi $ fmap (runFree g) f

    instance (Functor f) => Algebra f (Free f a) where
      phi = wrap

    instance (Functor f) => Monad (Free f) where
      return a = Free ($ a)
      m >>= f = fjoin $ fmap f m

    fjoin :: (Functor f) => Free f (Free f a) -> Free f a
    fjoin mma = Free $ \g -> runFree (runFree g) mma

现在我们可以使用Free构造functor的免费monad T a:

    data T a b = T a b b
    instance Functor (T a) where
      fmap f (T a l r) = T a (f l) (f r)

对于这个仿函数,我们可以为对象定义代数 [a]

    instance Algebra (T a) [a] where
      phi (T a l r) = l++(a:r)

一棵树是一个免费的monad over functor T a:

    type Tree a = Free (T a) ()

它可以使用以下函数构造(如果定义为ADT,它们是构造函数名称,所以没什么特别的):

    tree :: a -> Tree a -> Tree a -> Tree a
    tree a l r = phi $ T a l r -- phi here is for Algebra f (Free f a)
    -- and translates T a (Tree a) into Tree a

    leaf :: Tree a
    leaf = return ()

为了演示这是如何工作的:

    bar = tree 'a' (tree 'b' leaf leaf) $ tree 'r' leaf leaf
    buz = tree 'b' leaf $ tree 'u' leaf $ tree 'z' leaf leaf
    foo = tree 'f' leaf $ tree 'o' (tree 'o' leaf leaf) leaf

    toString = runFree (\_ -> [] :: String)

    main = print $ map toString [bar, buz, foo]

当runFree遍历要替换的树leaf ()时[],T a [a]所有上下文中的代数是构造表示树的有序遍历的字符串的代数.因为functor T a b构造一个新的树,它必须具有与larsmans引用的解决方案相同的内存消耗特性 - 如果树没有保存在内存中,一旦它们被表示整个的字符串替换,节点就会被丢弃子树.