Можно ли выполнить складывание в монаде состояния в постоянном стеке и пространстве кучи? Или другая функциональная техника лучше подходит для моей проблемы?

В следующих разделах описывается проблема и мотивирующий сценарий использования. Я'Я использую 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  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 тоже имеет эту проблему; переполнение стека только появляется сначала с меньшими коллекциями.)