Scalaz中State和Free单子的示例

Question

请问有人可以给一个如何使用ScalaZ Free monad的例子吗？

比如说，如果我有一个简单的State函数，并且想要应用它10,000次，那么就会得到StackOverflowError：

def setS(i: Int) :State[List[Int], Unit] = State { l => ( i::l, () ) }

val state = (1 to 10000).foldLeft( put(Nil :List[Int]) ) {
    case (st, i) => st.flatMap(_ => setS(i))
}

state(Nil)

据我理解，自由单子可以帮助避免这种情况。如何使用自由单子重写此代码段以避免堆栈溢出?

- Dragisa Krsmanovic

---

我建议阅读这篇文章 http://blog.higher-order.com/assets/trampolines.pdf - Noah

从我的经验来看，我本以为这种方法会起作用，但实际上并没有。今天我没有时间去研究它，但我很想看到答案。 - Travis Brown

因为某些原因，@TravisBrown的代码片段在使用Applicative而不是Monad来组合StateT时有效。https://gist.github.com/drstevens/3ea464446ee59463af1e - drstevens

@drstevens：不错！你应该把它作为答案，但我可以提一个新问题吗？ - Travis Brown

这里有一个新问题：https://dev59.com/KmAf5IYBdhLWcg3w52Pl。 - Travis Brown

Answer 1

正如我在上面的评论中所说，将State计算提升到StateT[Free.Trampoline, S, A]中似乎应该可行：

import scalaz._, Scalaz._, Free.Trampoline

def setS(i: Int): State[List[Int], Unit] = modify(i :: _)

val s = (1 to 10000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case (st, i) => st.flatMap(_ => setS(i).lift[Trampoline])
}

s(Nil).run

很遗憾，这仍然会导致堆栈溢出，但正如Dave Stevens所指出的那样，使用applicative *>而不是flatMap来进行顺序操作可以解决此问题：

val s = (1 to 100000).foldLeft(state[List[Int], Unit](()).lift[Trampoline]) {
  case (st, i) => st *> setS(i).lift[Trampoline]
}

s(Nil).run

我不确定为什么会这样，我已经提出了一个新问题，专门探讨这个差异，但是这应该能帮助你开始使用Free。

- Travis Brown