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

Несколько недель назад 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

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

Дэйв Стивенс просто указал, что последовательность с аппликативным *> вместо монадического 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, но по крайней мере там нет.)

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

Ответ 1

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

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

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

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) )

Calling liftF довольно уродлив, поэтому у меня есть PR, чтобы упростить для монахов штата и Клейсли, поэтому, надеюсь, в будущем не нужно будет вводить лямбда.

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

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

Ответ 2

Существует принципиальная интуиция для этой разницы.

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

/** 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) (Haskell GHC, безусловно, выполняет эту оптимизацию), но на данный момент это похоже на упущенную возможность оптимизации.

Ответ 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 не может помочь для StateT flatMap (а также map)...