[Haskell-cafe] Dynamically altering sort order

[wren ng thornton]

Denis Bueno wrote:
> Hi all,
> 
> Suppose I have the following interface to a sorting function:
> 
>     sort :: (Ord a) => [a] -> IO [a] -- sort large, on-disk array of records
> 
> but I don't have a sortBy where you can simply pass a compare function.

Why don't you have sortBy?


> Wrapped around this is a command-line program which should allow the
> user to specify different orderings on Records.  For example, if the
> Record has three fields, the user should be able to say "sort only on
> the first two".
> 
> Is there an Ord instance that can be dynamically changed in this way?

The only way to *dynamically* change the Ord instance is to have some 
language of newtypes wrapping records, each with and Ord instance. Then 
to have the user pass in a newtype name on the command line, parse that 
to know which constructor to use, map that constructor over the [a], and 
call sort.

If you had a sortBy function, this could be extended a good deal by 
developing an AST language for expressing sorting functions, and then 
the user could specify the whole AST on the command line, you could 
parse the string into an AST and then have a function to interpret the 
AST as a sorting function which you then pass to sortBy. Actually, this 
sounds like a fun little program to add to the Unix toolbox.



If, however, you wanted to (statically) derive a sortBy function given 
only the sort function, then you only need one Ord instance: namely one 
that packages up a comparison function with the values, as with your 
idea: (but...)

> My first idea is something like this:
> 
>     data CompareRecord = CR{ rCompare :: Record -> Record -> Ordering,
> unCR :: Record }
>     instance Ord CompareRecord where
>         compare (CR cmp x) (CR _ y) = cmp x y
> 
> where the rCompare field would be a function that is based on the
> flags passed to the command-line problem.  But this has an ugly
> asymmetry.

More than just an ugly asymmetry, it's easy to get bugs here because 
there's no assurance that we have the same comparison function packaged 
up on both sides, and so that means 'compare' is no longer commutative. 
If you define sortBy using the Schwartzian transform like Martijn 
suggested, though, then we can show that at least it's right for this 
use case.

-- 
Live well,
~wren