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

Question

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

这种遍历应该与深树状结构一起处理.

主要思想 - 从属元素应该根据一些"状态"生成.例如,标记为已显示元素的集合,以避免将来出现.

这是我最简单的实现

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于猫:

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

这里将详细讨论这种默认安全选择.