# PurelyFunctional.tv Newsletter 359: Tip: reduce as universal recursion over a list ### From OO to Clojure Workshop!

Issue 359 - January 06, 2020 · Archives · Subscribe

## Clojure Tip 💡

`reduce` as universal recursion over a sequence

We've been talking about recursion for a few weeks now and Ray asked about `reduce` as a form of universal recursion. It's a good question. `reduce` is often called universal recursion, but it must be qualified with "over a sequence". It's hard to write Fibonacci as a reduction. Give it a try and see what it looks like. However, recursing over a sequence is common, so it's a useful concept and can lead to much easier code.

Here's a common function we know and love. I'm talking about `map`.

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

Just to be sure, we've got a clear base case (when `ls` is empty, return the empty list) and the recursive case which makes progress (takes the `rest` of `ls` so that it will eventually be empty).

Now let's take a look at another function we love. This time, it's `filter`.

``````(defn filter [pred ls]
(if (empty? ls)
()
(if (pred (first ls))
(cons (first ls) (filter pred (rest ls)))
(filter pred (rest ls)))))
``````

Same deal. The base case checks if it's empty and returns the empty list. The recursive case is a little more complicated because of the conditional, but both branches make the same progress of calling `rest` on `ls`.

It turns out that this is a super common pattern when recursing down a list. The base case is the empty sequence (and it returns a constant value). The progress is moving one down the list.

Here's another example. This function sums the numbers in a list:

``````(defn sum [ls]
(if (empty? ls) ;; base case
0             ;; return constant
(+ (first ls)
(sum (rest ls))))) ;; recurse down rest
``````

This one makes another thing clearer: we are calling a specific function with two arguments. The first argument is the head of the list. The second argument is the recursive case. For `sum`, the function is `+`. So now we've got the parts to turn this implementation of `sum` into one that uses `reduce`.

``````(defn sum [ls]
(reduce + 0 ls))
``````

`+` is the function we were calling. `0` is the constant we return in the base case. And of course `ls` is the list we are recursing down.

The question is, can we do this for `map` and `filter`?

Here is `map` again.

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

We can see the constant return for the base case (empty list), but where is the function? Well, it's a little more complicated and mixed into the recursion. Here is `map` written in terms of `reduce`.

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

The function we pass to `reduce` is just calling `f` on the element `el` and consing it onto the list `ls'`. We know that `el` is the first element and `ls'` is the result of the recursion. We have passed the responsibility of destructuring the list and recursing to `reduce`. The empty list is just the value for our base case.

Now, if you run that function, it will actually reverse the list. I don't want to get into it now, but it has to do with our `map` function doing a right fold and `reduce` doing a left fold. To avoid the reversal, let's switch to using a vector instead of a list.

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

That's `map`. What about `filter`? Here's our original code again.

``````(defn filter [pred ls]
(if (empty? ls)
()
(if (pred (first ls))
(cons (first ls) (filter pred (rest ls)))
(filter pred (rest ls)))))
``````

Now let's look at the `reduce` version.

``````(defn filter [pred ls]
(reduce (fn [v el]
(if (pred el)
(conj v el)
v))
[] ls))
``````

That's really nice! Pulling out the function from the recursion really shows what we're doing. We add it to the vector if `pred` returns true, and don't if it returns `false`.

It turns out that `reduce` can do this for any similar recursion over a sequence. Do try out using `reduce` instead of recursion over a list. It's fun and one of the keys to going deeper with functional programming, since it's a higher order function.

## Clojure Challenge 🤔

### Last week's challenge

The challenge in Issue 358 was to implement dependency ordering for a project management app. You can see the submissions.

Although I got one complaint that the challenge was too easy, I got a ton of submissions. I want a lot of submissions, so I'll stick to that difficulty level.

### This week's challenge

words with duplicate letters

Some words have duplicate letters ("book"---two o's---or "that"---two t's). Many don't.

Your task is to write a predicate that returns `true` if the string contains any words with duplicate letters.

Examples:

`(duplicate-letter? "Hello, my friend!")` => `true` (because "hello" has two l's)

`(duplicate-letter? "Hey friend!")` => `false` (because no words have duplicates)

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