Ranking of Fruits

It is a gloomy Thursday morning, and you are hunched over your laptop. A simple programming exercise lies before you.

Given a list containing the names of several types of fruit:

names=["Cherry","Lime","Durian","Banana","Apple"]

Sort the list alphabetically.

With the deft keystrokes of a practiced hand, a scrap of JavaScript emerges in your text editor:

names.sort()

A dim pang of nausea. Perhaps it would be best to avoid in-place mutation? No problem; take your pick:

names.slice().sort()
names.toSorted()

Did I say alphabetically? I meant by length. For the moment, you set aside the worrisome fact that JavaScript’s built-in sorting functions do not guarantee a stable sort:

names.toSorted((x,y) => x.length - y.length)

Requirements continue to compound. Perhaps you also have a list of quantities which correspond to the original fruits:

sales=[22,5,97,12,1]

Now you must create a ranking of fruits, sorting the fruits by their sales count. This is not fundamentally a different problem, but the expression is less natural. One approach you might take is the decorate-sort-undecorate idiom, known in the Perl-o-sphere as the Schwartzian Transform:

names.map((x,i) => ({name:x, sales:sales[i]}))
     .sort((x,y) => y.sales - x.sales)
     .map(x => x.name)

In the ranking of fruits, a name which begins with the letter ‘D’ is forbidden. The origins of this law are beyond your ken and mine. Regardless, it is most efficient to filter out such elements before sorting, but, you realize, one must do so after decorating, to avoid mangling the correspondence between indices of names and sales:

names.map((x,i) => ({name:x, sales:sales[i]}))
     .filter(x => x.name[0] != 'D')
     .sort((x,y) => y.sales - x.sales)
     .map(x => x.name)

Perhaps it would be better to use a list-of-dictionaries representation for this data to begin with, and dispense with the map()s:

fruits=[
	{name:'Cherry',sales:22},
	{name:'Lime'  ,sales: 5},
	{name:'Durian',sales:97},
	{name:'Banana',sales:12},
	{name:'Apple' ,sales: 1},
]

fruits.filter(x => x.name[0] != 'D')
      .sort((x,y) => y.sales - x.sales)

Something about this convention gnaws at you, but you aren’t sure yet what it is.

You’re a K programmer now.

names:("Cherry";"Lime";"Durian";"Banana";"Apple")
sales:22 5 97 12 1

Alphabetic:

names@<names

By length:

names@<#:'names

By sales, descending:

names@>sales

What has changed here? K does not have a sort function per se; it offers the primitives grade up (<) and grade down (>). These verbs produce a permutation vector: more specifically, a list of indices by which the input could be indexed to place its items in order. Combined, an index and a grade form a sort. The APL tradition has cleaved one common algorithm into two composable parts.

Because grading is distinct from indexing in K, it is easy to sort one list by another; this renders decorate-sort-undecorate unnecessary in most cases. Flat, homogenous lists are mechanically sympathetic, and K guides the programmer toward this choice.

Filtering out the accursed D-fruits before sorting, however, ruins the elegance of your composition; each list must be filtered individually:

m:&~"D"=*:'names
names[m]@>sales[m]

With a muffled grunt you decide to perform the filter at the end instead:

("D"~*:)_names@>sales

Alas.

You’re a Lil programmer now.

Like its cousin Q, Lil contains a primitive collection type that is rare among scripting languages: tables. A table can be thought of as a dictionary of lists, all the same length. Turn your head 90 degrees about the proper axis and you can instead think of it as a list of dictionaries, all with the same keys. A table is both representations, and neither. The implicit relationships between elements of the input lists are made explicit in the structure of the table, and rectangularity is guaranteed by the datatype itself.

fruits:insert name sales with
     "Cherry" 22
     "Lime"    5
     "Durian" 97
     "Banana" 12
     "Apple"   1
end

You begin again.

Alphabetic:

select orderby name asc from fruits

By length:

select orderby count@name asc from fruits

By sales, descending:

select orderby sales desc from fruits

By sales, D-fruits banished¹:

select orderby sales desc where !name like "D*" from fruits

Each variation retains the same structure. The columns of the table are permuted together, and are filtered together. You have the conceptual flexibility of the pipeline of dictionaries in the JavaScript formulation, and the elegance (if not the concision) of the K formulation.

We have come to terms.

back