Blog

In this post we’ll continue the refactoring of our now-a-bit-more-elegant Scheme code for doing reports in our hypothetical Gift Card scenario. We will discover another fundamental building block in the functional programming world, a function that takes a list, and reduces it to a single value, using an user provided reducer function.

Together with the list filtering function developed in an earlier post in this series, and the list conversion function in the previous post, we’ll see how our more generic functions can help rewrite a couple of twenty-line problem-specific functions into one-liners, showing off the composability of functions, and hopefully help you increase your understanding of functional programming at the same time.

Aiming for perfection

Continuing our series of rewrites and generalizations, you notice that if you implement a date-minimizer called min-date you could also re-write oldest-used-here into a beautiful one-liner:

(define (oldest-used-here giftcards)
  (min-date (select issue-date (where used-here? giftcards))))

(min-date could internally use an earliest-date function, mentioned in the previous post, that would select the earliest date from its two parameters, but I’m not showing an implementation here)

However there’s something troubling you. Your refactoring-sense is tingling. While you’ve made good progress, you’re not quite there yet. You cannot quite put your finger on it, but there’s something you are missing. You are sure of it!

After a few hmm’s and ooh’s, and thatsnotit’s, you decide it’s the strange similarities yet differences between sum and min-date that’s bothering you. Both functions take a list of something (integers, and dates, respectively) and reduces this down to a single value (the sum, and the minimum date, respectively). Using this observation, could it then be possible to write a generic list-reducer-function somehow!?

After contemplating this insight for a while, you produce the following function in a burst of inspiration:

 1 ; the 'reduce' function turns a list into a single value using 
 2 ; a user-provided reducer function, and an initial seed value
 3 (define (reduce reducer current-value items)
 4   ; if there are no more items, return the current value
 5   (if (empty? items)
 6       current-value
 7       ; otherwise reduce the current value and the current item
 8       ; into a single value using the provided reducer function
 9       (let* ([current-item (first items)]
10              [remaining-items (rest items)]
11              [reduced-value (reducer current-value current-item)])
12         ; and recurse on the remaining items
13         (reduce reducer reduced-value remaining-items))))

(Notice that the reduce function didn’t need to define an iteration helper like we’ve used so many times now, as reduce already has all the parameters needed to simply recurse on itself.) Using the reduce function, you are able to re-write sum, and min-date as the following one-liners;

(define (sum numbers) (reduce + 0 numbers))
(define (min-date dates) (reduce earliest-date (current-date) dates))

I assume we have a current-date function, which is called without parameters to get todays date as a starting value for finding the minimum date. Obviously, if we are trying to find the minimum from a list of some future dates, “today” wouldn’t be a good starting value, would it. But in our given scenario we know we won’t have to deal with gift cards from the future (or will we, Mr. McFly?)

The value of uniformity

Also notice how in this example the sum function is able to use the addition function (+) in a way that for example C# cannot use its addition operator (+), as C# makes a language-level distinction between functions, expressions and operators, whereas these are interchangeable concepts in Lisp and Scheme, as well as in other functional programming languages, as it’s proven useful to be able to pass them around like this!

This version of reduce can handle being called with an empty list (or “the” empty list, as it’s normally called, as there’s really only one such list in existence in Scheme) in which case the user-provided value of current-value is returned. You could omit the current-value parameter, and let the reducer instead start off by reducing the first and second elements of the list (instead of the initial value and the first element of the list) but then it wouldn’t know what to return in case we called it with the empty list. But it would be a tad simpler to use.

If we wanted, we could implement this variation as, say, reduce1, calling reduce with the first item of the list as the initial value, but it will need at least one item to reduce:

(define (reduce1 reducer items) (reduce reducer (first items) (rest items)))

Eh, Reduce Me?

Perhaps it’s not clear how reduce does its job. In the case of the sum function, the accumulator (current-value) starts off at 0 and is then updated at each iteration with the sum of itself and the current number from the list, using + as our reducer. (And when I say “update” I don’t mean modified – the accumulator is immutable – but it’s getting a new value when passed into the next iteration!) For a three-element list (1 2 3), and an initial value of 0, the reduction basically becomes:

(+ (+ (+ 0 1) 2) 3)

In the case of the min-date function, we start off at “today”, and at each iteration finds the minumum date of the accumulator (current-value) and the current date from the list (using earliest-date as our reducer). If the current date from the list is later than the currently earliest date found, the accumulator won’t be updated. If an earlier date is found in the list than we’ve previously seen, the accumulator is then updated to this new value, and at the end of the iteration through the list, we have found the minimum date! The reduction then becomes:

(earliest-date (earliest-date (earliest-date init-val first-elem) second-elem) third-elem)

And so on…

Where are we now?

Over the last three posts, you’ve now devised and implemented “where”, “select” and “reduce”, and hopefully learned how to pass around functions as parameters, to specialize the workings of a generic algorithm. Congratulations! These are powerful tools, and fundamental building blocks in the world of functional programming. Use them for good, not for evil! Understanding them is a milestone towards getting a FP mindset! You are likely to use select and where fifty times more often than you’ll use reduce, however.

You should also know that in most, if not all, functional languages these functions, and several more, are already a part of the standard library, but perhaps under different names. where is often called “filter”, select is often called “map” and reduce is often called “fold” (or “foldL”, where L for the fact that it reduces in left-to-right order, which sometimes matters). It’s also likely that these library functions are more advanced than our implementations, for example including error handling, as well as versions that can handle additional input lists.

I’ve chosen other names here than the standard Scheme ones, for several reasons:

• increased clarity – at least in my opinion; ask someone what they think a function called “map” does, or if then believe a function that “filters” includes, or excludes the filtered items.
• similarity to SQL clauses – many “non-functional” Microsoft-class programmers already know SELECT and WHERE from writing SQL-syntax.
• similarity to their C#/.NET names (where they’re called Select, Where and Accumulate)

You should now be able to take over the world! Or at least, you won’t need to manually iterate through lists anymore, as these three functions should be able to cover most of your iteration needs for the next decade or two.