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 ?

Pennyroyal

I'd recommend giving this a read blog.higher-order.com/assets/trampolines.pdf – Heroics

Off the top of my head I'd expect this approach 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. – Fleur

@Heroics 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. – Pennyroyal

For some reason @TravisBrown's gist works when using Applicative instead of Monad to combine StateT. gist.github.com/drstevens/3ea464446ee59463af1e – Antibiosis

@drstevens: Nice! You should make that an answer, but mind if I ask it as a new question? – Fleur

@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. – Antibiosis

Here's a new question. – Fleur

@DragisaKrsmanovic , I answered the question here on how to use Free to avoid SO Exceptions. Hope this helps: https://mcmap.net/q/992564/-applicative-vs-monadic-combinators-and-the-free-monad-in-scalaz – Wellheeled

Answer 1

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.

Fleur