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

Question

的不同实现

此遍历应处理宽和深树状结构。

主要思想-从属元素应该根据一些"state"生成。例如一组 标记为可见的 元素以在将来避免它们。

这是我提供的最简单的实现

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

下降 WhosebugError。

有没有办法修复 DepthFirstState 的实现，这样即使在非常深的递归下，它也可以运行而无需 Whosebug？

Answer 1

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

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

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

虽然这不是（请注意 traverseS 与 State 的 traverseSTrampoline 相同）：

(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

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

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。

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

scalaz.State stack overflow in deep monadic loop

stack-overflow

scala

state-monad

scalaz