Аппликативные против монадических комбинаторов и свободная монада в Скалазе

Question

Пару недель назад Dragisa Krsmanovic задал вопрос о том, как использовать свободную монаду в Scalaz 7, чтобы избежать переполнения стека в этой ситуации (я немного адаптировал его код):

import scalaz._, Scalaz._

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

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

s(Nil)

Я думал, что просто поднимая батут вStateT должно сработать:

import Free.Trampoline

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

s(Nil).run

Но это все еще уносит стек, таким образом, я только отправил это как комментарий.

drstevens только что отметил, что последовательность с аппликативным *> вместо монадического flatMap на самом деле работает просто отлично:

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

s(Nil).run

(Ну, конечно, это очень медленно, потому что это цена, которую вы платите за то, что делаете что-то интересное в Scala, но, по крайней мере, переполнение стека не происходит.)

Что тут происходит? Я не думаю, что может быть принципиальная причина для этого различия, но на самом деле я понятия не имею, что может происходить в реализации, и у меня нет времени копаться в данный момент. Но мне любопытно, и было бы здорово, если бы кто-то еще знал.

Answer 1

Mandubian верен, flatMap StateT не позволяет вам обходить накопление стека из-за создания нового StateT непосредственно перед вызовом привязки обернутой монады (которая в вашем случае была бы Free[Function0]).

Так что батут не может помочь, но Free Monad над функтором для State является одним из способов обеспечения безопасности стека.

Мы хотим перейти от State[List[Int],Unit] к Free[a[State[List[Int],a],Unit], и наш вызов flatMap будет к flatMap Free (который не делает ничего, кроме create Свободная структура данных).

val s = (1 to 100000).foldLeft( 
    Free.liftF[({ type l[a] = State[List[Int],a]})#l,Unit](state[List[Int], Unit](()))) {
      case (st, i) => st.flatMap(_ => 
          Free.liftF[({ type l[a] = State[List[Int],a]})#l,Unit](setS(i)))
    }

Теперь у нас есть свободная структура данных, которую мы можем легко обработать как состояние:

s.foldRun(List[Int]())( (a,b) => b(a) )

Вызывать liftF довольно некрасиво, поэтому у меня есть пиар, чтобы облегчить монады State и Kleisli, так что, надеюсь, в будущем не понадобится лямбда типа.

Изменить: PR принят, так что теперь у нас есть

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

Answer 2

Для этого различия есть принципиальная интуиция.

Аппликативный оператор *> оценивает свой левый аргумент только для его побочных эффектов и всегда игнорирует результат. Это похоже (в некоторых случаях эквивалентно) на Haskell's >> функция для монад. Вот источник для *>:

/** Combine `self` and `fb` according to `Apply[F]` with a function that discards the `A`s */
final def *>[B](fb: F[B]): F[B] = F.apply2(self,fb)((_,b) => b)

а также Apply#apply2:

def apply2[A, B, C](fa: => F[A], fb: => F[B])(f: (A, B) => C): F[C] =
  ap(fb)(map(fa)(f.curried))

В общем, flatMap зависит от результата левого аргумента (это необходимо, так как это вход для функции в правом аргументе). Хотя в этом конкретном случае вы игнорируете левый результат, flatMap не знает этого

Вероятно, учитывая ваши результаты, что реализация для *> оптимизирован для случая, когда результат левого аргумента не нужен. тем не мение flatMap не может выполнить эту оптимизацию, и поэтому каждый вызов увеличивает стек, сохраняя неиспользованный левый результат.

Возможно, это можно было оптимизировать на уровне компилятора (scalac) или JIT (HotSpot) (GHC на Haskell, безусловно, выполняет эту оптимизацию), но сейчас это кажется упущенной возможностью оптимизации.

Answer 3

Просто чтобы добавить к обсуждению...

В StateT, у тебя есть:

  def flatMap[S3, B](f: A => IndexedStateT[F, S2, S3, B])(implicit F: Bind[F]): IndexedStateT[F, S1, S3, B] = 
  IndexedStateT(s => F.bind(apply(s)) {
    case (s1, a) => f(a)(s1)
  })

apply(s) исправляет текущее состояние ссылки в следующем состоянии.

bind определение охотно интерпретирует свои параметры, перехватывая ссылку, потому что это требуется:

  def bind[A, B](fa: F[A])(f: A => F[B]): F[B]

На разнице ap который может не нуждаться в интерпретации одного из его параметров:

  def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B]

С этим кодом Trampoline не могу помочь StateTflatMap (а также map)...