Clojure: сокращение, сокращение и бесконечные списки

Question

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

Какое значение вызывает сокращение или уменьшение в бесконечном списке?

(def c (cycle [0]))
(reduce + c)

Это быстро вызовет ошибку OutOfMemoryError.Кстати, (reduce + (cycle [0])) не генерирует ошибку OutOfMemoryError (по крайней мере, не в то время, пока я ждал).Это никогда не возвращается.Не уверен почему.

Есть ли способ вызвать уменьшение или уменьшение бесконечного списка таким образом, чтобы это имело смысл?Проблема, которую я вижу в приведенном выше примере, заключается в том, что в конечном итоге вычисляемая часть списка становится достаточно большой, чтобы переполнить кучу.Возможно, бесконечный список - не правильная парадигма.Сокращение по сравнению с генератором, потоком ввода-вывода или потоком событий имело бы больше смысла.Значение не должно сохраняться после его оценки и использования для изменения состояния.

Answer 1

Он никогда не вернется, потому что Reduce принимает последовательность и функцию и применяет эту функцию до тех пор, пока входная последовательность не станет пустой , только тогда она сможет узнать, что имеет окончательное значение.

Reduceна действительно бесконечном seq не будет иметь большого смысла, если он не производит побочный эффект, такой как регистрация его прогресса.

В первом примере вы сначала создаете переменную, ссылающуюся на бесконечную последовательность.

(def c (cycle [0]))

Затем вы передаете содержимое переменной var, чтобы уменьшить, что начинает чтение элементов для обновления его состояния.,

(reduce + c)

Эти элементы нельзя собирать, поскольку переменная c содержит ссылку на первый из них, который, в свою очередь, содержит ссылку на второй и так далее.В конце концов он читает столько места, сколько есть места в куче, а затем - OOM.

Чтобы не допустить переворота кучи во втором примере, вы не сохраняете ссылку на данные, которые вы уже использовали, поэтому элементы наПоследовательность, возвращаемая циклом, GCd так же быстро, как они создаются, и накопленный результат продолжает увеличиваться.В конечном итоге он переполнится долго и потерпит крах (clojure 1.3) или превратится в BigInteger и вырастет до размера всей кучи (clojure 1.2)

(reduce + (cycle [0]))

Answer 2

Ответ Артура хорош, насколько это возможно, но похоже, что он не отвечает на ваш второй вопрос о reductions. reductions возвращает ленивую последовательность промежуточных этапов того, что reduce вернул бы , если бы в списке содержалось только N элементов. Поэтому вполне разумно вызывать reductions в бесконечном списке:

user=> (take 10 (reductions + (range)))
(0 1 3 6 10 15 21 28 36 45)

Answer 3

Если вы хотите продолжать получать элементы из списка, например, поток ввода-вывода, и сохранять состояние между запусками, вы не можете использовать дозыq (без обращения к def ).Вместо этого хорошим подходом будет использование loop / recur , это позволит вам избежать использования слишком большого количества стекового пространства и позволит вам сохранить состояние, в вашем случае:

 (loop [c (cycle [0])]
   (if (evaluate-some-condition (first c))
     (do-something-with (first c) (recur (rest c)))
     nil))

Конечнопо сравнению с вашим случаем здесь есть проверка условия, чтобы убедиться, что мы не зациклились бесконечно.

Answer 4

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

В качестве альтернативы для такого рода ситуаций, вот полезная функция, которая сокращает только первые n элементов в последовательности, реализованная с использованием recur для разумной эффективности:

 (defn counted-reduce 
  ([n f s] 
    (counted-reduce (dec n) f (first s) (rest s) ))
  ([n f initial s]
    (if (<= n 0)
      initial
      (recur (dec n) f (f initial (first s)) (rest s)))))

(counted-reduce 10000000 + (range))
=> 49999995000000