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

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

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

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

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

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

Ответ 1

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

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

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

(def c (cycle [0]))

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

(reduce + c)

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

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

(reduce + (cycle [0]))

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

В качестве альтернативы для такого рода ситуаций, здесь полезная функция, которая сводит только первые 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