scala - 函数式风格提前退出深度优先递归

Question

我有一个关于以函数式风格编写递归算法的问题。我将在此处使用 Scala 作为示例，但该问题适用于任何函数式语言。

我正在对n二叉树进行深度优先枚举，其中每个节点都有一个标签和可变数量的子节点。这是一个打印叶节点标签的简单实现。

case class Node[T](label:T, ns:Node[T]*)
def dfs[T](r:Node[T]):Seq[T] = {
    if (r.ns.isEmpty) Seq(r.label) else for (n<-r.ns;c<-dfs(n)) yield c
}
val r = Node('a, Node('b, Node('d), Node('e, Node('f))), Node('c))
dfs(r) // returns Seq[Symbol] = ArrayBuffer('d, 'f, 'c)

现在说，有时我希望能够通过抛出异常来放弃解析超大树。这在函数式语言中可能吗？具体来说，在不使用可变状态的情况下这可能吗？这似乎取决于你所说的“超大”是什么意思。这是该算法的纯函数版本，当它尝试处理深度为 3 或更大的树时，它会抛出异常。

def dfs[T](r:Node[T], d:Int = 0):Seq[T] = {
    require(d < 3)
    if (r.ns.isEmpty) Seq(r.label) else for (n<-r.ns;c<-dfs(n, d+1)) yield c
}

但是，如果一棵树因为太宽而不是太深而变得过大怎么办？具体来说，如果我想在递归调用 dfs() 函数时抛出异常，无论递归的深度如何，该怎么办？我能看到如何做到这一点的唯一方法是拥有一个可变计数器，该计数器随着每次调用而递增。我不知道如何在没有可变变量的情况下做到这一点。

我是函数式编程的新手，并且一直在这样的假设下工作:可以用可变状态做的任何事情都可以在没有可变状态的情况下完成，但我在这里没有看到答案。我唯一能想到的就是编写一个 dfs() 版本，它以深度优先的顺序返回树中所有节点的 View 。

dfs[T](r:Node[T]):TraversableView[T, Traversable[_]] = ...

然后我可以通过说dfs(r).take(n)来施加我的限制，但我不知道如何编写这个函数。在 Python 中，我只是在访问节点时通过生成节点来创建一个生成器，但我不知道如何在 Scala 中实现相同的效果。 (Scala 相当于 Python 风格的 yield 语句，似乎是作为参数传入的访问者函数，但我不知道如何编写其中一个来生成序列 View 。)

编辑接近答案。

这是一个按深度优先顺序返回节点Stream的函数。

def dfs[T](r: Node[T]): Stream[Node[T]] = {
    (r #:: Stream.empty /: r.ns)(_ ++ dfs(_))
}

差不多就是这样了。唯一的问题是 Stream 会记住所有结果，这会浪费内存。我想要一个可遍历的 View 。以下是想法，但无法编译。

def dfs[T](r: Node[T]): TraversableView[Node[T], Traversable[Node[T]]] = {
    (Traversable(r).view /: r.ns)(_ ++ dfs(_))
}

它给出了“找到的TraversableView[Node[T], Traversable[Node[T]]]，必需的TraversableView[Node[T], Traversable[_]] ++ 运算符的错误。如果我将返回类型更改为 TraversableView[Node[T], Traversable[_]]，我会遇到与“相同的问题”发现”和“必需”子句交换了。所以有一些我还没有发现的魔法类型差异咒语，但这已经很接近了。

Answer 1

这是可以做到的:您只需编写一些代码即可按照您想要的方式实际迭代子级(而不是依赖 for)。

更明确地说，您必须编写代码来迭代子列表并检查“深度”是否超出了您的阈值。这是一些 Haskell 代码(很抱歉，我不太流利使用 Scala，但这可能很容易音译):

http://ideone.com/O5gvhM

在此代码中，我基本上将 for 循环替换为显式递归版本。如果访问的节点数量已经太深(即 limit 不是正数)，这允许我停止递归。当我递归检查下一个子节点时，我减去前一个子节点的 dfs 访问的节点数，并将其设置为下一个子节点的限制。

函数式语言很有趣，但它们与命令式编程相比是一个巨大的飞跃。它确实让你注意到状态的概念，因为当你发挥作用时，所有这些都在参数中极其明确。

编辑:对此进行更多解释。

我最终从“仅打印叶节点”(这是OP的原始算法)转换为“打印所有节点”。这使我能够通过结果列表的长度访问子调用访问的节点数量。如果你想坚持叶子节点，你必须携带你已经访问过的节点数量:

http://ideone.com/cIQrna

再次编辑为了澄清这个答案，我将所有 Haskell 代码放在 ideone 上，并将我的 Haskell 代码音译为 Scala，所以这可以留在这里作为明确的答案问题:

case class Node[T](label:T, children:Seq[Node[T]])

case class TraversalResult[T](num_visited:Int, labels:Seq[T])

def dfs[T](node:Node[T], limit:Int):TraversalResult[T] =
    limit match {
        case 0     => TraversalResult(0, Nil)
        case limit => 
            node.children match {
                case Nil => TraversalResult(1, List(node.label))
                case children => {
                    val result = traverse(node.children, limit - 1)
                    TraversalResult(result.num_visited + 1, result.labels)
                }
            }
    }

def traverse[T](children:Seq[Node[T]], limit:Int):TraversalResult[T] =
    limit match {
        case 0     => TraversalResult(0, Nil)
        case limit =>
            children match {
                case Nil => TraversalResult(0, Nil)
                case first :: rest => {
                    val trav_first = dfs(first, limit)
                    val trav_rest = 
                        traverse(rest, limit - trav_first.num_visited)
                    TraversalResult(
                        trav_first.num_visited + trav_rest.num_visited,
                        trav_first.labels ++ trav_rest.labels
                    )
                }
            }
    }

val n = Node(0, List(
    Node(1, List(Node(2, Nil), Node(3, Nil))),
    Node(4, List(Node(5, List(Node(6, Nil))))),
    Node(7, Nil)
))
for (i <- 1 to 8)
    println(dfs(n, i))

输出:

TraversalResult(1,List())
TraversalResult(2,List())
TraversalResult(3,List(2))
TraversalResult(4,List(2, 3))
TraversalResult(5,List(2, 3))
TraversalResult(6,List(2, 3))
TraversalResult(7,List(2, 3, 6))
TraversalResult(8,List(2, 3, 6, 7))

附注这是我第一次尝试 Scala，所以上面可能包含一些可怕的非惯用代码。对不起。