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.
(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))))))
map does something similar. Wrapping the code in
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.
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))
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
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 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
Relevant courses 📚
If you like recursion, laziness, and reduce, check out these courses.
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
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
You 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.
- 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.
nilif you can’t find the value.
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