Пример Государственной и Свободной монады в Скалазе

Question

Может кто-нибудь привести пример использования ScalaZ Free monad?

Например, если у меня есть простая функция State и я хочу применить ее 10 000 раз, я получу StackruError:

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)

Как я понимаю, Free monad может помочь избежать этого. Как бы я переписал этот кусок кода, используя свободную монаду, чтобы не вызвать переполнение стека?

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

К сожалению, это все еще переполняет стек, но, как отмечает Дейв Стивенс, последовательность с аппликативным *> вместо 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,