# PurelyFunctional.tv Newsletter 360: Tip: fold left vs fold right ### From OO to Clojure Workshop!

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.

## 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?

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.

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