Монадическая складка с Государственной монадой в постоянном пространстве (куча и стек)?
Можно ли выполнить складывание в монаде состояния в постоянном стеке и пространстве кучи? Или другая функциональная техника лучше подходит для моей проблемы?
В следующих разделах описывается проблема и мотивирующий сценарий использования. Я использую Scala, но решения в Haskell тоже приветствуются.
Сложите вState
Монада наполняет кучуПредположим, Скалаз 7. Рассмотрим монадическую складку в Государственной монаде. Чтобы избежать переполнения стека, мы будем батутировать сгиб.
import scalaz._
import Scalaz._
import scalaz.std.iterable._
import Free.Trampoline
type TrampolinedState[S, B] = StateT[Trampoline, S, B] // monad type constructor
type S = Int // state is an integer
type M[B] = TrampolinedState[S, B] // our trampolined state monad
type R = Int // or some other monoid
val col: Iterable[R] = largeIterableofRs() // defined elsewhere
val (count, sum): (S, R) = col.foldLeftM[M, R](Monoid[R].zero){
(acc: R, x: R) => StateT[Trampoline, S, R] {
s: S => Trampoline.done {
(s + 1, Monoid[R].append(acc, x))
}
}
} run 0 run
// In Scalaz 7, foldLeftM is implemented in terms of foldRight, which in turn
// is a reversed.foldLeft. This pulls the whole collection into memory and kills
// the heap. Ignore this heap overflow. We could reimplement foldLeftM to avoid
// this overflow or use a foldRightM instead.
// Our real issue is the heap used by the unexecuted State mobits.
Для большой коллекцииcol
, это заполнит кучу.
Я полагаю, что во время сгиба для каждого значения в коллекции создается закрытие (государственный мобит)x: R
параметр), заполняя кучу. Ни один из них не может быть оценен доrun 0
выполняется, обеспечивая исходное состояние.
Можно ли избежать такого использования O (n) кучи?
Более конкретно, может ли начальное состояние быть предоставлено до сгиба, чтобы монада состояний могла выполняться во время каждого связывания, а не вкладывать замыкания для последующей оценки?
Или можно сложить складку так, чтобы она выполнялась лениво после того, как государственная монадаrun
? Таким образом, следующийx: R
Закрытие не будет создано до тех пор, пока предыдущие не будут оценены и сделаны пригодными для сбора мусора.
Или есть лучшая функциональная парадигма для такой работы?
Пример приложенияНо, возможно, я использую не тот инструмент для работы. Эволюция примера использования приведена ниже. Я брожу по неправильному пути здесь?
Рассмотреть возможностьотбор проб из пластато есть, выбирая за один проход равномерный случайныйk
предметы из коллекции слишком велики, чтобы уместиться в памяти. В Scala такая функция может быть
def sample[A](col: TraversableOnce[A])(k: Int): Vector[A]
и если прыщ вTraversableOnce
Тип может быть использован как это
val tenRandomInts = (Int.Min to Int.Max) sample 10
Работа сделанаsample
по сутиfold
:
def sample[A](col: Traversable[A])(k: Int): Vector[A] = {
col.foldLeft(Vector()){update(k)(_: Vector[A], _: A)}
}
Тем не мение,update
с состоянием; это зависит отn
, количество предметов уже видел. (Это также зависит от ГСЧ, но для простоты я предполагаю, что это глобально и с сохранением состояния. Методы, используемые для обработкиn
будет распространяться тривиально.) Так как справиться с этим состоянием?
Нечистое решение простое и работает с постоянным стеком и кучей.
/* Impure version of update function */
def update[A](k: Int) = new Function2[Vector[A], A, Vector[A]] {
var n = 0
def apply(sample: Vector[A], x: A): Vector[A] = {
n += 1
algorithmR(k, n, acc, x)
}
}
def algorithmR(k: Int, n: Int, acc: 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
}
}
Но как насчет чисто функционального решения?update
должен взятьn
в качестве дополнительного параметра и вернуть новое значение вместе с обновленным образцом. Мы могли бы включитьn
в неявном состоянии накопитель складок, например,
(col.foldLeft ((0, Vector())) (update(k)(_: (Int, Vector[A]), _: A)))._2
Но это затемняет намерение; мы действительно намерены накапливать вектор выборки. Эта проблема, кажется, готова для Государственной монады и монадической левой складки. Давай еще раз попробуем.
Мы будем использовать Scalaz 7, с этим импортом
import scalaz._
import Scalaz._
import scalaz.std.iterable_
и работать надIterable[A]
, поскольку Скалаз не поддерживает монадическое сворачиваниеTraversable
.
sample
теперь определено
// sample using State monad
def sample[A](col: Iterable[A])(k: Int): Vector[A] = {
type M[B] = State[Int, B]
// foldLeftM is implemented using foldRight, which must reverse `col`, blowing
// the heap for large `col`. Ignore this issue for now.
// foldLeftM could be implemented differently or we could switch to
// foldRightM, implemented using foldLeft.
col.foldLeftM[M, Vector[A]](Vector())(update(k)(_: Vector[A], _: A)) eval 0
}
где обновление
// update using State monad
def update(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
}
}
К сожалению, это уносит стек в большую коллекцию.
Так что давайте батут это.sample
сейчас
// sample using trampolined State monad
def sample[A](col: Iterable[A])(k: Int): Vector[A] = {
import Free.Trampoline
type TrampolinedState[S, B] = StateT[Trampoline, S, B]
type M[B] = TrampolinedState[Int, B]
// Same caveat about foldLeftM using foldRight and blowing the heap
// applies here. Ignore for now. This solution blows the heap anyway;
// let's fix that issue first.
col.foldLeftM[M, Vector[A]](Vector())(update(k)(_: Vector[A], _: A)) eval 0 run
}
где обновление
// update using trampolined State monad
def update(k: Int) = {
(acc: Vector[A], x: A) => StateT[Trampoline, Int, Vector[A]] {
n => Trampoline.done { (n + 1, algorithmR(k, n + 1, acc, x) }
}
}
Это устраняет переполнение стека, но по-прежнему создает кучу для очень больших коллекций (или очень маленьких куч). Одна анонимная функция на значение в коллекции создается во время сгиба (я думаю, что закрывать по каждойx: A
параметр), потребляя кучу, прежде чем батут даже запустить. (FWIW, версия State тоже имеет эту проблему; переполнение стека только появляется сначала с меньшими коллекциями.)