Clojure: reduce, reductions and infinite lists

Question

Reduce and reductions let you accumulate state over a sequence. Each element in the sequence will modify the accumulated state until the end of the sequence is reached.

What are implications of calling reduce or reductions on an infinite list?

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

This will quickly throw an OutOfMemoryError. By the way, (reduce + (cycle [0])) does not throw an OutOfMemoryError (at least not for the time I waited). It never returns. Not sure why.

Is there any way to call reduce or reductions on an infinite list in a way that makes sense? The problem I see in the above example, is that eventually the evaluated part of the list becomes large enough to overflow the heap. Maybe an infinite list is not the right paradigm. Reducing over a generator, IO stream, or an event stream would make more sense. The value should not be kept after it's evaluated and used to modify the state.

Answer 1

It will never return because reduce takes a sequence and a function and applies the function until the input sequence is empty, only then can it know it has the final value.

Reduce on a truly infinite seq would not make a lot of sense unless it is producing a side effect like logging its progress.

In your first example you are first creating a var referencing an infinite sequence.

(def c (cycle [0]))

Then you are passing the contents of the var c to reduce which starts reading elements to update its state.

(reduce + c)

These elements can't be garbage collected because the var c holds a reference to the first of them, which in turn holds a reference to the second and so on. Eventually it reads as many as there is space in the heap and then OOM.

To keep from blowing the heap in your second example you are not keeping a reference to the data you have already used so the items on the seq returned by cycle are GCd as fast as they are produced and the accumulated result continues to get bigger. Eventually it would overflow a long and crash (clojure 1.3) or promote itself to a BigInteger and grow to the size of all the heap (clojure 1.2)

(reduce + (cycle [0]))