Blog

Now we are going to write some Scheme code in order to show off some features of functional programming. (As stated earlier, I’m actually using the Scheme-dialect Racket, but that shouldn’t matter too much for the discussion at hand.) We’re going to write some code, refactor it into more reusable parts, and hopefully become enlightened when we discover the power of passing a function as a parameter to another function.

Let’s write some code, already!

Let’s assume you are given an assignment to create a number of reports for a small retail chain, regarding the use of their Gift Cards. As a programming exercise you decide to do them in Scheme (since on-the-job training is something you have to do every now and then to keep sharp, right?)

The base data you have is a list of gift cards; gift card ID, issuing store, date of issue, and amount. If the card has been used there’s also the using store, and date of usage. You decide that the first thing to do is to write a Scheme procedure that gives you the sum of all gift cards issued at a particular store, and then move on to more complex queries.

I’m going to skip some parts, such as how you would read your base data from a file or database. (As a side note, I’m using the words ‘procedure’ and ‘function’ to both mean the same thing; a “subroutine” of a larger program).

The resulting code turns out something like this:

 1 ; get the sum of all gift card issued by my store (id "SE1")
 2 (define (sum-issued-here giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (sum-issued-here-iterator remaining-giftcards accumulated-sum)   
 6     ; if there are no more gift cards, return the accumulated sum
 7     (if (empty? remaining-giftcards)
 8         accumulated-sum
 9         ; otherwise, process the current gift card
10         (let* ([current-gc (first remaining-giftcards)]
11                [still-remaining-gcs (rest remaining-giftcards)]
12                ; if this was my card, update the sum, otherwise keep it the same
13                [new-sum (if (string=? "SE1" (issuing-store current-gc))
14                             (+ accumulated-sum (amount current-gc))
15                             accumulated-sum)])
16           ;  and recurse on the remaining items
17           (sum-issued-here-iterator still-remaining-gcs new-sum))))
18   
19   ; call the helper function with initial values
20   (sum-issued-here-iterator giftcards 0))

I’ll try to explain what this code does. It’ll help if you do understand most of what it does. At line 1 we define a function called sum-issued-here that takes a list of gift cards as input. Then line 5-17 defines a helper function called sum-issued-here-iterator (which is not visible outside the definition of sum-issued-here) that does the actual work, and the helper function is then called at line 20 to give the result of the procedure. In Scheme, there’s no return keyword (or function). Instead the return value of a function is the value of the last expression evaluated. The same is true for most other scheme statements.

The workings of the helper function

The helper function is built on a very common pattern in functional programming; recursive decomposition. Here the problem is divided into two parts, first perform some work on the first element of a list (lines 13-15), and then recurse (line 17) to solve a smaller sub-problem (the work on the remaining items), until you reach the base case when the list is empty (line 7) which ends the recursion. In this case the helper is constructing the answer using an accumulator that is updated in each recursion, and then returned in the base case (line 8).

At line 10-13, we bind three identifiers to their values using a variant of let, called let*:

• current-gc is bound to the first element of the remaining-giftcards list
• still-remaining-gcs is bound to a list with the subsequent elements of the remaining-giftcards list (all but the first)
• new-sum is updated, or not, depending on which store issued the current gift card. For simplicity, you’ve decided to hard code the ID of your nearest store, “SE1”.

The functions amount and issuing-store are property accessor functions for the gift card structure, they obviously return the amount, and the issuing store, respectively, for the provided gift card (their definitions are trivial and not shown). string=? and empty? are simple predicate functions (returning true or false) testing for string equality and the empty list, respectively. 

Note that we’re not actually updating any “variables”. Everything is immutable, and no values are harmed during the execution of these functions. It may seem like we update the accumulator at least, but in effect, a new accumulator is created at each step, based on the value of the previous accumulator.

You may suspect that this function could cause a stack overflow error if given a really long list, but that won’t happen. We’re not actually using up any stack space for our recursion, regardless of how many times the function calls itself. This is because the above helper function is tail-recursive, which in Scheme is as efficient as a standard iterative loop! So it is really pure iteration, coded as a recursive algorithm.

Your second report, and a Déjà Vu

You then continue implementing a completely different report function, one that should give you the earliest issue-date for all gift cards used in a particular store. When you look at the resulting implementation, you cannot help but notice that it is more or less identical to the previous one:

 1 ; get the earliest issue-date for all gift card used in my store (id "SE1")
 2 (define (oldest-used-here giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (oldest-used-here-iterator remaining-giftcards minimum-date)   
 6     ; if there are no more gift cards, return the minimum date found
 7     (if (empty? remaining-giftcards)
 8         minimum-date
 9         ; otherwise, process the current gift card
10         (let* ([current-gc (first remaining-giftcards)]
11                [still-remaining-gcs (rest remaining-giftcards)]
12                ; if this was used here, update the minimum-date, otherwise keep it the same
13                [new-minimum-date (if (string=? "SE1" (using-store current-gc))
14                                      (earliest-date minimum-date (issue-date current-gc))
15                                      minimum-date)])
16           ;  and recurse on the remaining items
17           (oldest-used-here-iterator still-remaining-gcs new-minimum-date))))
18   
19   ; call the helper function with initial values
20   (oldest-used-here-iterator giftcards today))

Really, the only differences are that it calls different functions in a few cases. These new functions should be fairly self-explanatory; using-store and issue-date are two additional property accessor functions for the gift card structure, and earliest-date is a “minimum” function for dates, and so returns the smallest/earliest of two dates.

Refactoring functionally

At this point, you are thinking that this probably could be refactored in some way, but it’s not immediately clear what kind of rewrite would let us share parts of the implementation for our gift card report functions. As a first rewrite, you decide that you could probably implement a separate function for the part of the first report that finds gift cards for a particular store, and returns a list of such gift cards.

This already filtered list could then be used as the input for a rewritten, simpler version of the sum-issued-here function you wrote earier, that don’t have to test each gift card for inclusion, and it could be used for several other report functions that do work on lists of cards issued “here”. But it won’t be useful for the “oldest-used-here”-function, as that one needs a list of gift-cards used (not issued) in a particular store (bummer!).

Nevertheless you write something like this:

 1 ; get a list of gift cards issues in my store
 2 (define (issued-here giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (issued-here-iterator remaining-giftcards result)
 6     ; if there are no more gift cards, return the minimum date found
 7     (if (empty? remaining-giftcards)
 8         result 
 9         ; otherwise, process the current gift card
10         (let* ([current-gc (first remaining-giftcards)]
11                [still-remaining-gcs (rest remaining-giftcards)]
12                ; if this was my card, include it in the result, otherwise not
13                [new-result  (if (string=? "SE1" (issuing-store current-gc))
14                                 (cons current-gc result)
15                                 result)])
16           ;  and recurse on the remaining items
17           (issued-here-iterator still-remaining-gcs new-result))))
18   
19   ; call the helper function with initial values
20   (issued-here-iterator giftcards empty))

Now, where have I seen this before? Hey wait a minute! This silly silly function keeps repeating itself with only minor variations! This time the accumulator is also a list, and we’re using a function called cons which is the list constructor. It creates a new list by placing the current-gc in front of the (initially empty) result list. The biggest change is perhaps that we no longer try to get at a property of the gift card, and instead work on the gift card itself.

And then, finally, enlightenment!

What happens next is that you, out of the blue, are struck by a lambda-shaped lightning bolt of pure functional enlightenment! It makes you feel great! Parenthesis suddenly seem like the best thing since curly braces, and prefix arithmetic now seems… less awkward.

You then suddenly realize, why oh why didn’t you see this earlier, that you could parameterize this damned function with another function! It’s just so obvious now! Then you could control what it actually does inside the loop, and have it dance to your tune! It no longer needs to be specifically for finding particular gift-cards, it can do anything, everything, mo ha ha ha!

After coming to your senses, you promptly rewrite it so:

 1 ; the 'where' function could probably prove useful, as its filtering
 2 ; behavior is controlled by the user-supplied predicate? function!
 3 (define (where predicate? list-of-items)
 4   ; our well-known helper
 5   (define (where-iterator remaining-items results)
 6     (if (empty? remaining-items)
 7         (reverse results) ; restore original ordering
 8         (let* ([current-item (first remaining-items)]
 9                [still-remaining (rest remaining-items)]
10                ; We're now letting the predicate? function decide
11                ; if the current-item should be included or not!
12                [new-results (if (predicate? current-item)
13                                 (cons current-item results)
14                                 results)])
15           (where-iterator still-remaining new-results))))
16 
17   ; call the helper function with initial values
18   (where-iterator list-of-items empty))

Now, this function is quite general and useful! It takes a list, and builds a new list containing all items for which the function passed in returns true. The ability to use functions like this, the same way you can use say a number (passing it as a parameter to another function, storing it in a variable, and returning it as a result from a function) is perhaps the defining characteristic of functional programming.

Note that as the list constructor function cons puts new items at the front of the list we need to reverse the result list as the last step, in order to keep the result in the same order as the original list, which seems like a good thing to do. It didn’t really matter in our earlier implementations.

Putting ‘where’ to work

You then write two simple one-liners; a predicate function issued-here? that checks if the provided gift card was issued at the “SE1” store or not, and another called used-here? that checks if the provided gift card was used at the “SE1” store or not.

(define (issued-here? gc) (string=? "SE1" (issuing-store gc)))
(define (used-here? gc) (string=? "SE1" (using-store gc)))

You can then use them together with your new where-function like this:

(sum-amount (where issued-here? giftcards))
(sum-amount (where used-here? giftcards))

to sum the giftcards issued, or used, at the “SE1” shop! Wonders upon functional wonders! This is the kind of code we’d like to write! Will you ever need to see a recursive helper function again, you wonder! In the next post, we’ll try to continue our refactoring of our Gift Card report functions, and show the definition of the sum-amount function used above.