Recurse.se Yada yada on Software Development

25Jan/120

Select Your Weapon

This entry is part 4 of 5 in the series Towards Functional Programming

In this post we’ll continue the refactoring of our less-than-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 converts each element into a new form using an user provided conversion function.

Together with the list filtering function developed in the previous post in this series, and a simple list-of-numbers summer, 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.

Refactoring continued

In our previous post, we saw that in Scheme (or any functional programming language) using a function as a parameter to another function can be very useful, and helps separating generic behavior from the specifics needed for a particular situation. We implemented a generic list filtering method we called where, that let the user provide the filtering rules used by passing in a function that decides which elements to include, and which to exclude.

As you now have the useful where function, you can now redefine the sum-issued-here function (also introduced in the previous post) as a slightly more generic amount-summer-function plus the where-function to find the gift cards to sum. The amount-summer can be defined like this:

 1 ; sum the amounts of all gift card in the list
 2 (define (sum-amount giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (sum-amount-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                ; get the amount from the gift card, and update the sum
13                [new-sum (+ accumulated-sum (amount current-gc))])
14           ;  and recurse on the remaining items
15           (sum-amount-iterator still-remaining-gcs new-sum))))
16   
17   ; call the helper function with initial values
18   (sum-amount-iterator giftcards 0))

It’s very much like several of the other functions you’ve written (and please see the previous post for a thorough explanation of the recursive iteration helper function). The difference from the original implementation is the fact that this function sums all provided gift cards, as you can now use a separate function to decide which gift cards to sum, which have greatly improved the composability of our functions. By composability I mean that we can compose (combine) them in several different ways to get different results.

We can now rewrite sum-issued-here simply as:

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

using the one-line function issued-here? we defined in the previous post, to find us the relevant cards to sum. Now the sum-issued-here cannot become much simpler, but the oldest-used-here function (defined in the previous post, but basically finds the oldest gift card (the one with the earliest issue-date) used in a particular shop) is still in need of a rewrite. While we can use the where function to do part of the job, we cannot re-use much else. We’d rather not write yet-another similar function.

Further ideas for refactoringsThe Wrench Connection

You have a gut feeling that there’s more generic functionality waiting to get extracted, that would let you rewrite many of your previous functions. Thinking hard about this, considering the definition of the sum-amount and the oldest-used-here functions, combined with your new-found insight that it’s possible to parameterize a function with a different function (something we just put to excellent use in our where function), you come up with a few different options for further refactorings:

  • Write a more generic summer, where the property to be summed is controlled by a user-supplied function, for example; (sum-by amount giftcards)
  • Write a generic list converter, where the conversion is controlled by a user-supplied function, so that you could convert a list of gift cards into a list of issue-dates, or amounts.
  • Write a generic summer of a list of numbers, that could then be used to sum those amounts
  • Along the same lines, you’d need a date-minimizer, to find the earliest date among a list of issue-dates

After a short session of guru meditation, you decide a generic list converter function would be a most beautiful and useful companion to your generic list filtering function, as well as being more composable than sum-by, and thus you start with that one. You decide to name it the select function.

Select - A generic list converter function

Your implementation of the select function turns out much like many other functions in this series, based on the same recursive decomposition of the problem, first work in the current item, and then recurse on the rest of the items.

 1 ; the 'select' function converts each item in a list into a new form.
 2 ; the conversion is done by the user-supplied convert function! 
 3 (define (select convert list-of-items)
 4   ; our well-known helper
 5   (define (select-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                ; let the passed-in function convert each item into
11                ; a new form and preprend it to the accumulated results
12                [new-results  (cons (convert current-item) results)])
13           ;  and recurse on the remaining items
14           (select-iterator still-remaining new-results))))
15           
16   ; call the helper function with initial values
17   (select-iterator list-of-items empty))

This is an immensely useful function. It may appear just like many other, but you’ll use it time and time again when using functional programming techniques. I’d say it’s one of the most fundamental building blocks of functional code. You’ll use it to convert lists of item-IDs to item objects, using a database lookup function, or to convert from items to XML that you’ll write to a file, and many other things.

Pillow, pillow on the bed, will I ever rest my head?With this masterpiece done, do you pat yourself on the back? Do you take a well deserved nap? No, there’s no stopping you now, and you proceed relentlessly even though your eyes burn from lack of sleep, by re-writing sum-amount (defined at the top of this post) into a generic summer of a list of numbers.

After briefly considering the name ‘reginald’, you rename it sum. It really only needs a trivial change on line 13, to replace the call to the amount function with the current list element itself (and perhaps a few identifiers could use more generic names, as the sum function is no longer gift-card specific). You decide to spare the readers the sight of the actual implementation.

The revised implementation of sum-issued-here is more interesting:

(define (sum-issued-here giftcards)
  (sum (select amount (where issued-here? giftcards))))

This is quite beautiful! Using a few generic and very composable functions and your initial 20-line function has become a one-liner (ok, it’s a two-liner, but the line break is for readability, OK?) with the aid of a few helpers such as amount and issued-here? – also one-liners.

Step by step

The way this version of sum-issued-here works is that if it is called with a list of gift cards, we’ll call them gc1, gc2 and gc3, it will return the sum of the amounts of those issued in a particular shop nearby (as per our definition in the previous post).

  1. The list of gift cards is passed on to the where function that returns a new list, including only those gift cards for which the issued-here? function returns true. Let’s say that was true for gc1 and gc3, but not gc2.
  2. This list with gc1 and gc3 is then passed to the select function, that calls the amount function on each gift card, to extract their amounts into a new list that it returns. This list of amounts (well, plain numbers really) now contains say 250, and 175.
  3. This list of numbers is passed on to the sum function that sums it up into the number 425, which then becomes the return value of this particular call to sum-issued-here.

In the next post, we’ll try to finalize this refactoring session after discovering yet another useful function, so that we can move on to solve a larger and more challenging problem.