Another Programming Idiom You've Never Heard Of

New programmers quickly pick-up how array indexing works. You fetch an element like this: array[3]. (More experienced folks can amuse themselves with the equally valid 3[array] in C.) Now here's a thought: what if you could fetch multiple values at the same time and the result was a new array?

Let's say the initial array is this:

10 5 9 6 20 17 1

Fetching the values at indices 0, 1, 3, and 6, gives:

10 5 6 1

In the J language you can actually do this, though the syntax likely isn't familiar:

0 1 3 6 { 10 5 9 6 20 17 1

The list of indices is on the left, and the original array on the right. That awkwardly unmatched brace is the index operator. (You can also achieve the same end in the R language, if you prefer.)

This may seem like a frivolous extension to something you already knew how to do, but all of a sudden things have gotten interesting. Now indexing can be used for more than just indexing. For example, you can delete elements by omitting indices. This drops the first two elements:

2 3 4 5 6 { 10 5 9 6 20 17 1

Or how about reversing an array without needing a special primitive:

6 5 4 3 2 1 0 { 10 5 9 6 20 17 1

This last case is particularly significant, because the indices specify a permutation of the original array. Arrange the indices however you want, and you can transform an array to that order.

In J, there's an operator that's like a sort, except the result specifies a permutation: a list of where each element should go. Using the same "10 5 9..." array, that first element should be in position 4, the value 5 should be in position 1, and so on. Here's the whole array of permuted indices.

6 1 3 2 0 5 4

What good is that? If you use that list of indices on the left side of the "{" operator with the original array on the right, you sort the array:

6 1 3 2 0 5 4 { 10 5 9 6 20 17 1

Now imagine you've got two other parallel arrays that you want to keep in sync with the sorted one. All you do is use that same "sorted permutation" array to index into each of the other arrays, and you're done.

(If you liked this, you might enjoy the original A Programming Idiom You've Never Heard Of.)

permalink June 6, 2012

Another Programming Idiom You've Never Heard Of

previously

archives