函数式早期退出深度优先递归 [英] Functional style early exit from depth-first recursion

问题描述

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

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

  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对于（n <-r.ns; c <-dfs（n））产生c 
} 
 val r =节点（'a，节点（'b，节点''） e，Node（'f））），Node（'c））
 dfs（r）//返回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））产生c 
} 
  

但是如果一棵树因为太宽而不是太深而过大会怎么样？具体来说，如果我想抛出一个异常，那么不管递归有多深，递归地调用 dfs（）函数时，都是 n 我可以看到如何做到这一点的唯一方法是让每个调用都有一个可变计数器。我不明白如何在没有可变变量的情况下做到这一点。

我是函数式编程的新手，一直在假设你可以用mutable状态可以没有，但我在这里没有看到答案。我唯一能想到的就是编写一个版本的 dfs（），以深度优先的顺序返回树中所有节点的视图。

  dfs [T]（r：Node [T]）：TraversableView [T，Traversable [_]] = ... 
  

然后我可以用 dfs（r）.take（n） code>，但我看不到如何编写这个函数。在Python中，我只是在我访问它们时创建了一个由 yield ing节点生成的生成器，但我没有看到如何在Scala中实现相同的效果。 （Scala相当于一个Python风格的 yield 语句似乎是一个作为参数传入的访问函数，但我无法弄清楚如何编写其中一个）



编辑接近答案。

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

  def dfs [T]（r：Node [T]）：Stream [Node [T]] = {
（r＃:: Stream.empty /：r.ns）（_ ++ dfs _））
} 
  

差不多就是这样。唯一的问题是 Stream 记忆所有结果，这是浪费内存。我想要一个可穿越的视图。

  def dfs [T]（r：Node [T]）：TraversableView [Node [T]，Traversable [Node [T]]] = {
（Traversable（r）.view /：r.ns）（_ ++ dfs（_））
} 
  

它给出了found TraversableView [Node [T]，Traversable [Node [T] ] ， TraversableView [Node [T]，Traversable [_]] 错误 ++ operator。如果我将返回类型更改为 TraversableView [Node [T]，Traversable [_]] ，我遇到了与found相同的问题， required子句切换了，所以还有一些我还没有点亮的魔术类型变体咒语，但是这是非常接近的。 解决方案

以下实现了对树中节点的深度优先搜索。

  import collection.TraversableView 
 case class节点[T]（标签：T，ns：节点[T] *）
 def dfs [T]（r：节点[T]）：TraversableView [Node [T]，Traversable [Node [T]]] = 
（ Traversable [Node [T]]（r）.view /：r.ns）{
（a，b）=> （a ++ dfs（b））。asInstanceOf [TraversableView [Node [T]，Traversable [Node [T]]]] 
} 
  

以深度优先的顺序打印所有节点的标签。

  val r = Node（'a，Node（'b，Node（'d），Node（'e，Node（'f））），Node（'c））
 dfs（r）.map（_ .label）.force 
 //返回Traversable [Symbol] = List（'a，'b，'d，'e，'f，'c）
  

这也是一样的，在3个节点被访问后退出。

  dfs（r）.take（3）.map（_。label）.force 
 //返回Traversable [Symbol] = List（'a，'b，'d）
  

如果您只需要叶节点，您可以使用 filter 等等注意， dfs 函数的fold子句需要一个明确的 asInstanceOf / code>转换。请参阅在Scala中键入方差错误时对可穿越视图进行foldLeft来讨论需要此功能的Scala打字问题。

I have a question about writing recursive algorithms in a functional style. I will use Scala for my example here, but the question applies to any functional language.

I am doing a depth-first enumeration of an n-ary tree where each node has a label and a variable number of children. Here is a simple implementation that prints the labels of the leaf nodes.

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)

Now say that sometimes I want to be able to give up on parsing oversize trees by throwing an exception. Is this possible in a functional language? Specifically is this possible without using mutable state? That seems to depend on what you mean by "oversize". Here is a purely functional version of the algorithm that throws an exception when it tries to handle a tree with a depth of 3 or greater.

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
}

But what if a tree is oversized because it is too broad rather than too deep? Specifically what if I want to throw an exception the n-th time the dfs() function is called recursively regardless of how deep the recursion goes? The only way I can see how to do this is to have a mutable counter that is incremented with each call. I can't see how to do it without a mutable variable.

I'm new to functional programming and have been working under the assumption that anything you can do with mutable state can be done without, but I don't see the answer here. The only thing I can think to do is write a version of dfs() that returns a view over all the nodes in the tree in depth-first order.

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

Then I could impose my limit by saying dfs(r).take(n), but I don't see how to write this function. In Python I'd just create a generator by yielding nodes as I visited them, but I don't see how to achieve the same effect in Scala. (Scala's equivalent to a Python-style yield statement appears to be a visitor function passed in as a parameter, but I can't figure out how to write one of these that will generate a sequence view.)

EDIT Getting close to the answer.

Here is an function that returns a Stream of nodes in depth-first order.

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

That is almost it. The only problem is that Stream memoizes all results, which is a waste of memory. I want a traversable view. The following is the idea, but does not compile.

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

It gives a "found TraversableView[Node[T], Traversable[Node[T]]], required TraversableView[Node[T], Traversable[_]] error for the ++ operator. If I change the return type to TraversableView[Node[T], Traversable[_]], I get the same problem with the "found" and "required" clauses switched. So there's some magic type variance incantation I haven't lit upon yet, but this is close.

解决方案

The following implements a lazy depth-first search over nodes in a tree.

import collection.TraversableView
case class Node[T](label: T, ns: Node[T]*)
def dfs[T](r: Node[T]): TraversableView[Node[T], Traversable[Node[T]]] =
  (Traversable[Node[T]](r).view /: r.ns) {
    (a, b) => (a ++ dfs(b)).asInstanceOf[TraversableView[Node[T], Traversable[Node[T]]]]
  }

This prints the labels of all the nodes in depth-first order.

val r = Node('a, Node('b, Node('d), Node('e, Node('f))), Node('c))
dfs(r).map(_.label).force
// returns Traversable[Symbol] = List('a, 'b, 'd, 'e, 'f, 'c)

This does the same thing, quitting after 3 nodes have been visited.

dfs(r).take(3).map(_.label).force
// returns Traversable[Symbol] = List('a, 'b, 'd)

If you want only leaf nodes you can use filter, and so forth.

Note that the fold clause of the dfs function requires an explicit asInstanceOf cast. See "Type variance error in Scala when doing a foldLeft over Traversable views" for a discussion of the Scala typing issues that necessitate this.

这篇关于函数式早期退出深度优先递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！