PurelyFunctional.tv Newsletter 360: Tip: fold left vs fold right

Issue 360 - January 13, 2020 · Archives · Subscribe

Clojure Tip 💡

fold left vs fold right

In the last issue, I mentioned that our map implementation was doing a right fold, whereas reduce in Clojure does a left fold. This is an important distinction because although both right and left folds can calculate the same values, they do it in opposite directions. The direction determines whether the recursion is tail-recursive or not, and thus affects the stack usage and whether it can be lazy. Let's dive into this.

Here is map:

(defn map [f ls]
  (if (empty? ls)
    ()
    (cons (f (first ls))
          (map f (rest ls)))))

Notice that the recursive call is not in tail position. That means we are consing onto the result of the tail call after the tail call returns. If you imagine the call stack in your head, you'll see that this implementation of map will walk down the entire list from left to right, then on the way back down the stack, builds the list up one cons at a time. Because it is left to right, it is called a right fold.

The way we implemented this function, it is eager. It is not lazy. If we had a very long list, we could blow the stack. Each call to map makes another call to map, so it's at least one stack frame per element in the list. We can easily fix that in Clojure by making it lazy.

(defn map [f ls]
  (lazy-seq
    (if (empty? ls)
      ()
      (cons (f (first ls))
            (map f (rest ls))))))

Clojure's built-in map does something similar. Wrapping the code in lazy-seq makes map return a lazy sequence. Notice that each call to map has its return value wrapped in lazy-seq, which is what makes this work. lazy-seq simply defers calling its body until the next item is needed. map can now be called on long lists, even infinitely long lists, without blowing the stack.

To summarize: map is a right fold. It uses non-tail recursion and can be made lazy.

Now let's contrast that to reduce. Here is a simple implementation.

(defn reduce [f init ls]
  (if (empty? ls)
    init
    (recur f (f init (first ls)) (rest ls))))

The most obvious difference is that reduce uses tail recursion. This is a classic left fold. Remember, map recursed first, then did the work (of consing), reduce does the work (of calling f), then recurses. That's what makes the directions opposite. When we implemented map in terms of reduce, our first implementation got the items backwards.

(defn map [f ls]
  (reduce (fn [ls' el]
            (cons (f el) ls'))
          () ls))

We had to replace the list with a vector so we were adding to the end. That fixed the order problem.

(defn map [f ls]
  (reduce (fn [v el]
            (conj v (f el)))
          [] ls))

But because reduce is a left fold, it can't be lazy. This implementation of map would go into an infinite loop if we applied it to an infinite list.

Last issue, we said "reduce is universal recursion over a list". Maybe we should say "reduce is universal tail recursion over a list". It's really an iterative algorithm, as we saw in Issue 357.

Can we write a right fold version of reduce?

We sure can.

(defn reduce-right [f init ls]
  (if (empty? ls)
    init
    (f (reduce-right f init (rest ls)) (first ls))))

That's quite a function to study and sit with for a while. It may make it easier to see how we could implement a correctly ordered map using it.

(defn map [f ls]
  (reduce-right (fn [ls' el]
                  (cons (f el) ls'))
                () ls))

Notice that it's the same anonymous function we passed to reduce before to implement map. But this one builds the cons cells correctly.

There's one problem: our reduce-right is eager and non-tail recursive! That means it will blow up on long lists. We can easily fixt that by wrapping the recursion in a lazy-seq. Since lazy-seq only works for collections, we should create a new function that makes that clear.

(defn reduce-right-lazy [f init ls]
  (lazy-seq
    (if (empty? ls)
      init
      (f (reduce-right f init (rest ls)) (first ls)))))

Now use that to implement map and you've got yourself a lazy sequence function. You can also implement filter.

Relevant courses 📚

If you like recursion, laziness, and reduce, check out these courses.

• Recursion 101
• Lazy Sequences
• Reduce Mini-Course

State of Clojure Community Survey 📋

Please support the ongoing development of Clojure by filling out the annual survey.

This survey has been going on for years and it collects very important statistics on the Clojure community. I find the information valuable myself. I can only imagine how important it would be for the folks in Clojure's core team to know this stuff.

Please fill it out, regardless of how you use Clojure. It's all great information.

Cognitect analyzes the data and produces a summary. Here is the one from last year. They also release all of the data. Daniel Compton also analyzes the free-text responses and writes a summary. Here is his from last year.

Clojure Challenge 🤔

Last week's challenge

The challenge in Issue 359 was to detect whether a sentence has words with duplicate letters. You can see the submissions.

Lots of great submissions this week, with many different approaches. Do check them out! I'm going to continue with this difficulty level. It seems to be working.

This week's challenge

Where's Waldo?

Yo u are given a vector of vectors, representing a grid. The grid is filled with values. Your job is to find a given value and return the path into the grid that will get to it.

Here's an example:

(wheres-waldo :W ;; look for :W
 [[:A :B :C]
  [:D :E :F]
  [:G :H :I]
  [:J :K :L]
  [:M :N :O]
  [:P :Q :R]
  [:S :T :U]
  [:V :W :X]
  [:Y :and :Z]]);=> [7 1]

Notice that I can pass [7 1] to get-in to find the value.

Notes

• The nested vectors will all be the same length. This is a rectangular grid.
• If the value occurs more than once, you can return coordinates to any of them.
• Return nil if you can't find the value.

Bonus

Can you make it work with arbitrarily nested vectors of different sizes?

Have fun with this one! Try out different ways to implement it.

Thanks to to this site for the challenge idea!

As usual, please reply to this email and let me know what you tried. I'll collect them up and share them in the next issue. If you don't want me to share your submission, let me know.

Rock on! Eric Normand