Example of State and Free monad in Scalaz

Question

Can somebody give an example how to use ScalaZ Free monad ?

For example, if I have a simple State function and want to apply it 10,000 times, I'd get 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)

As I understand, Free monad can help avoid this. How would I re-write this piece of code using Free monad to not cause stack overflow ?

I'd recommend giving this a read http://blog.higher-order.com/assets/trampolines.pdf — Noah, May 31 '14 at 03:51
Off the top of my head I'd expect [this approach](https://gist.github.com/travisbrown/58f289c69ac74d2e6d7e) to work, but it doesn't. I don't have time to look into it today, but I'll be curious to see an answer. — Travis Brown, May 31 '14 at 13:42
@Noah that's the exact article that prompted me to try this. I know, for this particular example, you can do it by using traverseS. But my question is more generic, I am using a collection just to illustrate problem. — Dragisa Krsmanovic, Jun 01 '14 at 18:09
For some reason @TravisBrown's gist works when using Applicative instead of Monad to combine StateT. https://gist.github.com/drstevens/3ea464446ee59463af1e — drstevens, Jun 10 '14 at 21:31
@drstevens: Nice! You should make that an answer, but mind if I ask it as a new question? — Travis Brown, Jun 10 '14 at 21:51
@TravisBrown Knock yourself out. I'm confused by it too. I was tempted to ask the scalaz list but I've already wasted too much time on this today. — drstevens, Jun 10 '14 at 21:58
[Here's a new question](http://stackoverflow.com/q/24151771/334519). — Travis Brown, Jun 10 '14 at 22:24
@DragisaKrsmanovic , I answered the question here on how to use Free to avoid SO Exceptions. Hope this helps: http://stackoverflow.com/a/24846694/25658 — Vincent, Jul 21 '14 at 21:20

score 4 · Accepted Answer · edited May 23 '17 at 11:48

As I say in a comment above, lifting the State computations into StateT[Free.Trampoline, S, A] seems like it ought to work:

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

Unfortunately this still overflows the stack, but as Dave Stevens notes, sequencing with the applicative *> instead of flatMap fixes the issue:

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

s(Nil).run

I'm not sure why this is, and I've asked a new question specifically about the difference, but that should get you started with Free.

Example of State and Free monad in Scalaz

1 Answers1

Linked