PurelyFunctional.tv Newsletter 360: Tip: fold left vs fold right
From OO to Clojure Workshop!
Watch my free workshop to help you learn Clojure faster and shift your paradigm to functional.
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
(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
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
lazy-seq simply defers calling its body until the next item
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
recurses. That's what makes the directions opposite. When we implemented
map in terms of
reduce, our first implementation got the items
(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
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
(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
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
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
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.
- 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