CODEWITHSUNDEEP
clojure
yalis
yalis

Reputation: 1518

Clojure: reduce, reductions and infinite lists

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.

Upvotes: 13

Views: 5788

Answers (4)

mikera
mikera

Reputation: 106401

As others have pointed out, it doesn't make sense to run reduce directly on an infinite sequence, since reduce is non-lazy and needs to consume the full sequence.

As an alternative for this kind of situation, here's a helpful function that reduces only the first n items in a sequence, implemented using recur for reasonable efficiency:

 (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

Upvotes: 0

pyr
pyr

Reputation: 424

If you want to keep getting items from a list like an IO stream and keep state between runs, you cannot use doseq (without resorting to def's). Instead a good approach would be to use loop/recur this will allow you to avoid consuming too much stack space and will let you keep state, in your case:

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

Of course compared to your case there is here a condition check to make sure we don't loop indefinitely.

Upvotes: 2

Arthur Ulfeldt
Arthur Ulfeldt

Reputation: 91617

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]))

Upvotes: 17

amalloy
amalloy

Reputation: 92147

Arthur's answer is good as far as it goes, but it looks like he doesn't address your second question about reductions. reductions returns a lazy sequence of intermediate stages of what reduce would have returned if given a list only N elements long. So it's perfectly sensible to call reductions on an infinite list:

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

Upvotes: 12

Related Questions