scalaz.State 深度单子(monad)循环中的堆栈溢出

Question

我正在尝试 Depth-First Search 的不同实现与 scalaz .

这种遍历应该处理宽和深的树状结构。

主要思想 - 应根据某些“状态”生成从属元素。例如 的集合标记为已查看 元素，以在将来避免它们。

这是我带来的最简单的实现

import scalaz._
import scalaz.syntax.monad._
import scalaz.State._

abstract class DepthFirstState[E, S] {
  def build(elem: E): State[S, List[E]]

  def go(start: E): State[S, List[E]] = for {
    xs ← build(start)
    ys ← xs.traverseSTrampoline(go)
  } yield start :: ys.flatten
}

我们可以创建最简单的算法来测试它如何处理深度搜索

class RangeSearchState extends DepthFirstState[Int, Int] {
  def build(elem: Int) = get[Int] map (limit ⇒ if (elem < limit) List(elem + 1) else Nil)
}

它只是一个降级为链表的树，其中每个元素 i有独生子女 i+1直到到达 limit编码在状态。虽然状态没有改变，但它更多 Reader比 State但事实并非如此。

现在

new RangeSearchState go 1 run 100

成功建立遍历号码列表。尽管

new RangeSearchState go 1 run 1000

与 StackOverflowError 坠落.

有没有办法修复 DepthFirstState 的实现所以它可以在没有 StackOverflow 的情况下运行即使是非常深的递归？

Answer 1

发生在 traverseSTrampoline 的蹦床保护您在遍历期间不会溢出堆栈。例如，这会爆炸:

import scalaz._, scalaz.std.list._, scalaz.syntax.traverse._

(0 to 10000).toList.traverseU(_ => State.get[Unit]).run(())

虽然这不是(注意 traverseS 与 traverseSTrampoline 的 State 相同):

(0 to 10000).toList.traverseS(_ => State.get[Unit]).run(())

但是，您只能在遍历期间获得这种保护，并且在您的情况下，由于递归调用而发生溢出。您可以通过手动进行蹦床来解决此问题:

import scalaz._
import scalaz.std.list._
import scalaz.syntax.traverse._

abstract class DepthFirstState[E, S] {
  type TState[s, a] = StateT[Free.Trampoline, s, a]

  def build(elem: E): TState[S, List[E]]

  def go(start: E): TState[S, List[E]] = for {
    xs <- build(start)
    ys <- xs.traverseU(go)
  } yield start :: ys.flatten
}

class RangeSearchState extends DepthFirstState[Int, Int] {
  def build(elem: Int): TState[Int, List[Int]] =
    MonadState[TState, Int].get.map(limit =>
      if (elem < limit) List(elem + 1) else Nil
    )
}

进而:

val (state, result) = (new RangeSearchState).go(1).run(10000).run

值得注意的是，此堆栈安全性内置于 State在 cats :

import cats.state.State
import cats.std.function._, cats.std.list._
import cats.syntax.traverse._

abstract class DepthFirstState[E, S] {
  def build(elem: E): State[S, List[E]]

  def go(start: E): State[S, List[E]] = for {
    xs <- build(start)
    ys <- xs.traverseU(go)
  } yield start :: ys.flatten
}

class RangeSearchState extends DepthFirstState[Int, Int] {
  def build(elem: Int): State[Int, List[Int]] =
    State.get[Int].map(limit => if (elem < limit) List(elem + 1) else Nil)
}

val (state, result) = (new RangeSearchState).go(1).run(10000).run

这个默认安全的选择被详细讨论了 here .