How do we do both left and right folds in Clojure?

Question

Reduce works fine but it is more like fold-left. Is there any other form of reduce that lets me fold to right ?

Answer 1

The reason that the clojure standard library only has fold-left (reduce) is actually very subtle and it is because clojure isn't lazy enough to get the main benefit of fold-right.

The main benefit of fold-right in languages like haskell is that it can actually short-circuit. If we do foldr (&&) True [False, True, True, True, True] the way that it actually gets evaluated is very enlightening. The only thing it needs to evaluate is the function and with 1 argument (the first False). Once it gets there it knows the answer and does not need to evaluate ANY of the Trues.

If you look very closely at the picture:

you will see that although conceptually fold-right starts and the end of the list and moves towards the front, in actuality, it starts evaluating at the FRONT of the list.

This is an example of where lazy/curried functions and tail recursion can give benefits that clojure can't.

Bonus Section (for those interested)

Based on a recommendation from vemv, I would like to mention that Clojure added a new function to the core namespace to get around this limitation that Clojure can't have the lazy right fold. There is a function called reduced in the core namespace which allows you to make Clojure's reduce lazier. It can be used to short-circuit reduce by telling it not to look at the rest of the list. For instance, if you wanted to multiply lists of numbers but had reason to suspect that the list would occasionally contain zero and wanted to handle that as a special case by not looking at the remainder of the list once you encountered a zero, you could write the following multiply-all function (note the use of reduced to indicate that the final answer is 0 regardless of what the rest of the list is).

(defn multiply-all [coll]
  (reduce
   (fn [accumulator next-value]
     (if (zero? next-value)
       (reduced 0)
       (* accumulator next-value)))
   1
   coll))

And then to prove that it short-circuits you could multiply an infinite list of numbers which happens to contain a zero and see that it does indeed terminate with the answer of 0

(multiply-all
 (cycle [1 2 3 4 0]))

Answer 2

Let's look at a possible definition of each:

(defn foldl [f val coll]
  (if (empty? coll) val
    (foldl f (f val (first coll)) (rest coll))))

(defn foldr [f val coll]
  (if (empty? coll) val
    (f (foldr f val (rest coll)) (first coll))))

Notice that only foldl is in tail position, and the recursive call can be replaced by recur. So with recur, foldl will not take up stack space, while foldr will. That's why reduce is like foldl. Now let's try them out:

(foldl + 0 [1 2 3]) ;6
(foldl - 0 [1 2 3]) ;-6
(foldl conj  [] [1 2 3]) ;[1 2 3]
(foldl conj '() [1 2 3]) ;(3 2 1)

(foldr + 0 [1 2 3]) ;6
(foldr - 0 [1 2 3]) ;-6
(foldr conj  [] [1 2 3]) ;[3 2 1]
(foldr conj '() [1 2 3]) ;(1 2 3)

Is there some reason you want to fold right? I think the most common usage of foldr is to put together a list from front to back. In Clojure we don't need that because we can just use a vector instead. Another choice to avoid stack overflow is to use a lazy sequence:

(defn make-list [coll]
  (lazy-seq
    (cons (first coll) (rest coll))))

So, if you want to fold right, some efficient alternatives are

1. Use a vector instead.
2. Use a lazy sequence.
3. Use reduced to short-circuit reduce.
4. If you really want to dive down a rabbit hole, use a transducer.