Friday, November 19, 2010

TAG-SortFunctions

Since the introduction of SymbolValue and Block culling, one of the things I've chased is how to do this same style of programming with sorting. For most sorting cases, you have a series of objects that you want to sort on some particular attribute. Maybe a sequence of customers you'd like to sort by name.

So it's tempting to want to add a series of APIs like those we added at Key Technology. This was a sortedBy: method, and was implemented something like
sortedBy: aSingleArgBlock
^self sorted: [:a :b | (aSingleArgBlock value: a) < (aSingleArgBlock value: b)]


The problems with this approach are a couple.

First you end up paralleling any of the existing 2 arg block sorting APIs. So if you have sorted: method, you add the sortedBy: method, as above. And then when you have a sort: method, you have to add a sortBy: method. And when you have a reverseSort: method, you add a reverseSortBy: method. Ad continuum.

Second, it doesn't capture the direction of the sort at all. It assumes you want to sort ascending. For descending, you'll have to implement even more methods.

Third, it doesn't capture chained sorting patterns at all. For example, what if I want to sort customers by first their last name, then their first name. I've seen a couple sites, where they add yet more multi argument sorting methods to the system to capture stacks of sorting criterion.

I sat down last night, and with tests, put together a TAG-SortFunctions package, published in the Cincom Public Repository. The basic idea was to use an object. Time and time and time again over the years, I rediscover the principle "there's an object waiting to be birthed here!" What this package does in principle is note that sorting by 2 arg blocks, doesn't have to be limited to 2 arg blocks. It's really about the value:value: interface. And we can introduce an object type that stands in for the simple block which captures the failings listed above.

Here's some examples.

Sort customers by last name in descending order.
customers asSortedCollection: [:each | each lastName] sortDown

Sort customers by last name in ascending order, and then by first name in ascending order.
customers sorted: [:each | each lastName] sortUp , [:each | each firstName] sortUp
or
customers sorted: [:each | each lastName] sortUp , [:each | each firstName]
(the second sortUp is taken care of automatically)

We don't have to stick to blocks either, we can use symbols. Here's an example that sorts a list of points by their x value in ascending order, but their y value in descending order.
points sort: #x sortUp, #y sortDown

Some things to note.

First, we don't have to add any new sorting APIs to the system. Just use the existing ones. Second, direction is easy to specify. The magic is all in the #sortUp/#sortDown methods. Third, we can express chains of sorting criterion by concatenating them with the , method.

If this is useful to others, I'll make it more usable, by pulling the tests out of the package so it doesn't need SUnitToo. And you can lobby Cincom to include it in VisualWorks. Or port it to your own flavor of Smalltalk. I did my best to write it in such a way that it would work in Squeak or Gemstone, or whatever.

6 comments:

  1. yeah, absolutely lovely. I've found the implementation of comparison methods (like the < and <= method) and blocks extremely annoying when it comes to sorting by multiple attributes. Having the sortUp and sortDown methods together with the comma method seems so totally easy to use.

    Thanks a lot for that!

    ReplyDelete
  2. Is there a way for a non-Cincom user to get the package? I wouldn't mind giving it a whirl in Squeak!

    ReplyDelete
  3. Ah, very nice, indeed. I've already replicated this into our local store. I'm all for splitting tests into separate package though not to have to carry SUnitToo in our runtime images. Cheers!

    ReplyDelete
  4. Travis, very very nice and clean!

    ReplyDelete
  5. Hi Travis, i made a simple port to Squeak/Pharo by roughly copy/pasting the latest version of code found on public store to http://smalltalkhub.com/mc/nice/NiceVMExperiments/main.
    But you didn't mention any license, could you tell which one you want to apply?

    ReplyDelete