PurelyFunctional.tv Newsletter 359: Tip: reduce as universal recursion over a list

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