scalaz Батут и IO

Этот вопрос связан с другим вопросом, но сводится к гораздо более простому случаю:

Я предполагаю следующий импорт:

import scalaz._, Scalaz._
import Free._, effect._

У меня есть следующие генераторы:

val fromOneIO: () => IO[Int] = {
  var i = 0; () => { i += 1; IO(i) }
} 
val fromOne: () => Int = {
  var i = 0; () => { i += 1; i }
}

и следующие нехвостовые рекурсивные определения:

def rec(i: Int): Int = {
  if (i == 0) {
    fromOne()
  } else {
    rec(i - 1) + fromOne()
  }
}
def rec1(i: Int): Trampoline[Int] = {
  if (i == 0) {
    Return(fromOne())
  } else {
    suspend {
      for {
        a <- rec1(i - 1)
        b <- Return(fromOne()): Trampoline[Int]
      } yield a + b
    }
  }
}
def recio(i: Int): Trampoline[IO[Int]] = {
  if (i == 0) {
    Return(fromOneIO())
  } else {
    suspend {
      for {
        ioa <- recio(i - 1)
        iob <- Return(fromOneIO()): Trampoline[IO[Int]]
      } yield {
        for (a <- ioa; b <- iob) yield a + b
      }
    }
  }
}

Результат:

rec(100) // overflows for arg 10000
rec1(10000).run // works
recio(10000).run.unsafePerformIO() //overflows

Как сделать так, чтобы IO map/flatMap тоже прыгали на трамплин? Кажется, у меня есть другие вложенные стеки, созданные внутри второго для понимания. Нужно ли мне писать TrampolineT, который будет использовать unsafePerformIO, и преобразовывать извлеченное значение ввода-вывода в приостановку?


scala scalaz scalaz7
person huynhjl    schedule 23.04.2013    source источник
comment
В этом конкретном примере экземпляр Monoid для IO[A: Monoid], кажется, работает. То есть просто измените свой оператор yield на ioa |+| iob. Однако для более широкой картины мне нечего порекомендовать.   -  person folone    schedule 23.04.2013
comment
На самом деле проблема, похоже, в экземпляре Monad для IO. Если вы используете его экземпляр Applicative, он работает нормально. yield (ioa |@| iob){_ + _}   -  person folone    schedule 23.04.2013
comment
Вы хотите, чтобы сам IO был батутом, а не функция, выстраивающая огромную цепочку вложенных IO действий. Ваш код позволяет вам создать действие IO без переполнения стека, но то, как вы его создаете, приведет к переполнению стека при запуске действия IO.   -  person Mysterious Dan    schedule 23.04.2013
comment
@folone, интересно, что аппликатив не переполняется. Я пытался отследить его, но не смог найти реализацию F.lift2. Я бы хотел, чтобы у scalaz7 все еще был источник с перекрестными ссылками, построенный на основе рентгеновского снимка Харры.   -  person huynhjl    schedule 24.04.2013
comment
@MyseriousDan, ну, мне все еще нужно иметь дело с тем фактом, что recio не является хвостовой рекурсией. Так что мне как бы нужно два уровня батута. Итак, мой вопрос на самом деле заключается в том, как добиться этого второго для IO.   -  person huynhjl    schedule 24.04.2013

Ответы (1)


arrow_upward
3
arrow_downward

Итак, IO(_) уже батут, чего бы это ни стоило. В дополнение к предложению от folone, я могу избежать переполнения, изменив второй for следующим образом:

val s = for (a <- ioa; b <- iob) yield a + b
val s1 = s.unsafePerformIO()
IO(s1)

Или вот так:

IO(for (a <- ioa; b <- iob) yield a + b).flatMap(identity)

Также IO(_) принимает параметр по имени, поэтому IO(expr) и val e = expr; IO(e) ведут себя по-разному. Это переполнит!

val s = for (a <- ioa; b <- iob) yield a + b
IO(s.unsafePerformIO())

Таким образом, хотя это не очень удовлетворительный ответ, кажется, что использование аппликативного падежа, где это возможно, или обертывание другим IO и выравнивание были бы обходными путями для взрыва стека.

person huynhjl    schedule 24.04.2013