Монадическая справка с государственной монадой в постоянном пространстве (куча и стопка)?

Ответ 1

Наша реальная проблема - это куча, используемая неисполненными государственными мобилями.

Нет, это не так. Реальная проблема заключается в том, что коллекция не вписывается в память и что foldLeftM и foldRightM вынуждают всю коллекцию. Побочным эффектом нечистого решения является то, что вы освобождаете память, когда идете. В "чисто функциональном" решении вы ничего не делаете.

Ваше использование Iterable игнорирует важную деталь: какая коллекция col на самом деле, как ее элементы создаются и как они должны быть отброшены. И так, обязательно, foldLeftM на Iterable. Это, вероятно, слишком строго, и вы заставляете всю коллекцию запоминать. Например, если это Stream, то до тех пор, пока вы держитесь за col, все элементы, которые были задействованы до сих пор, будут в памяти. Если это какой-то другой ленивый Iterable, который не memoize его элементов, то складка все еще слишком строгая.

Я попробовал ваш первый пример с EphemeralStream, не увидев какого-либо значительного давления кучи, хотя у него, очевидно, будут одинаковые "невыполненные госбюджеты". Разница в том, что элементы EphemeralStream слабо ссылаются и ее foldRight не заставляет весь поток.

Я подозреваю, что если вы использовали Foldable.foldr, вы бы не увидели проблемное поведение, так как оно сбрасывается с помощью функции, которая ленина во втором аргументе. Когда вы вызываете сгиб, вы хотите, чтобы он вернул подвеску, которая выглядит примерно так:

Suspend(() => head |+| tail.foldRightM(...))

Когда батут возобновляет первую подвеску и доходит до следующей подвески, все распределения между подвесками станут доступными для освобождения сборщиком мусора.

Попробуйте следующее:

def foldM[M[_]:Monad,A,B](a: A, bs: Iterable[B])(f: (A, B) => M[A]): M[A] =
  if (bs.isEmpty) Monad[M].point(a)
  else Monad[M].bind(f(a, bs.head))(fax => foldM(fax, bs.tail)(f))

val MS = StateT.stateTMonadState[Int, Trampoline]
import MS._

foldM[M,R,Int](Monoid[R].zero, col) {
  (x, r) => modify(_ + 1) map (_ => Monoid[R].append(x, r))
} run 0 run

Это будет работать в постоянной куче для батутной монады M, но переполнит стек для не-батуминой монады.

Но реальная проблема заключается в том, что Iterable не является хорошей абстракцией для данных, которые слишком велики для размещения в памяти. Конечно, вы можете написать настоятельную боковую программу, в которой вы явно отбрасываете элементов после каждой итерации или использовать ленивую правую складку. Это хорошо работает, пока вы не захотите составить эту программу с другой. И я предполагаю, что вся причина, по которой вы изучаете это в монаде State, чтобы начать, - это получить композиционность.

Так что вы можете сделать? Вот несколько вариантов:

• Использовать Reducer, Monoid и его состав, затем запустить в обязательном явном свободном цикле (или бамбуковой ленивой правой складке) в качестве последнего шага, после чего композиция невозможна или ожидается.
• Используйте Iteratee композицию и монадическую Enumerator, чтобы их прокормить.
• Напишите преобразователи композиционных потоков с Scalaz-Stream.

Последний из этих параметров - тот, который я бы использовал и рекомендовал в общем случае.

Ответ 2

Использование State или любой аналогичной монады не является хорошим подходом к проблеме. Использование State обречено на удар стек/кучу на больших коллекциях. Рассмотрим значение x: State[A,B], построенное из большой коллекции (для например, свернув его). Тогда x можно оценить по разным значениям начального состояния A, давая разные результаты. Поэтому x необходимо сохранить всю информацию содержащихся в сборнике. В чистых настройках x не может забыть некоторые информации, чтобы не взорвать стек/кучу, поэтому все, что вычисляется, остается в до тех пор, пока не будет освобождено все монадическое значение, которое произойдет только после результат оценивается. Таким образом, потребление памяти x пропорционально размеру коллекции.

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

Я попытался использовать Scalaz Iteratees, но кажется, что эта часть еще не зрелая, она страдает от, как это делает State (или, возможно, я не использую ее правильно, код доступен здесь, если кому-то интересно).

Однако, это было просто, используя мою (еще немного экспериментальную) scala-conduit библиотека ( отказ от ответственности: я автор):

import conduit._
import conduit.Pipe._

object Run extends App {
  // Define a sampling function as a sink: It consumes
  // data of type `A` and produces a vector of samples.
  def sampleI[A](k: Int): Sink[A, Vector[A]] =
    sampleI[A](k, 0, Vector())

  // Create a sampling sink with a given state. It requests
  // a value from the upstream conduit. If there is one,
  // update the state and continue (the first argument to `requestF`).
  // If not, return the current sample (the second argument).
  // The `Finalizer` part isn't important for our problem.
  private def sampleI[A](k: Int, n: Int, sample: Vector[A]):
                  Sink[A, Vector[A]] =
    requestF((x: A) => sampleI(k, n + 1, algorithmR(k, n + 1, sample, x)),
             (_: Any) => sample)(Finalizer.empty)


  // The sampling algorithm copied from the question.
  val rand = new scala.util.Random()

  def algorithmR[A](k: Int, n: Int, sample: Vector[A], x: A): Vector[A] = {
    if (sample.size < k) {
      sample :+ x // must keep first k elements
    } else {
      val r = rand.nextInt(n) + 1 // for simplicity, rand is global/stateful
      if (r <= k)
        sample.updated(r - 1, x) // sample is 0-index
      else
        sample
    }
  }

  // Construct an iterable of all `short` values, pipe it into our sampling
  // funcition, and run the combined pipe.
  {
    print(runPipe(Util.fromIterable(Short.MinValue to Short.MaxValue) >->
          sampleI(10)))
  }
}

Обновление:. Можно решить проблему с помощью State, но нам нужно реализовать специальную складку специально для State, которая знает, как сделать это постоянным пространством:

import scala.collection._
import scala.language.higherKinds
import scalaz._
import Scalaz._
import scalaz.std.iterable._

object Run extends App {
  // Folds in a state monad over a foldable
  def stateFold[F[_],E,S,A](xs: F[E],
                            f: (A, E) => State[S,A],
                            z: A)(implicit F: Foldable[F]): State[S,A] =
    State[S,A]((s: S) => F.foldLeft[E,(S,A)](xs, (s, z))((p, x) => f(p._2, x)(p._1)))


  // Sample a lazy collection view
  def sampleS[F[_],A](k: Int, xs: F[A])(implicit F: Foldable[F]):
                  State[Int,Vector[A]] =
    stateFold[F,A,Int,Vector[A]](xs, update(k), Vector())

  // update using State monad
  def update[A](k: Int) = {
    (acc: Vector[A], x: A) => State[Int, Vector[A]] {
        n => (n + 1, algorithmR(k, n + 1, acc, x)) // algR same as impure solution
    }
  }

  def algorithmR[A](k: Int, n: Int, sample: Vector[A], x: A): Vector[A] = ...

  {
    print(sampleS(10, (Short.MinValue to Short.MaxValue)).eval(0))
  }
}