🚀 go-pugleaf

Chris Holt    >
Dan Bernstein >>

>>And, as a first sample problem to be solved by a typing system: How do
>>we write a generic, type-safe sorting routine?

>What would be nice would be something of the form
>Sort S <=
>    where S : sequence of D
>          D : domain
>         <= : partial_order (D x D -> boolean)
>            where partial_order : transitive & reflexive & antisymmetric
>Of course, partial_order would be part of the standard toolbox of the
>programmer; it maps the domain of dyadic D-to-boolean operations to
>that subset satisfying the given properties.

If you're going to sort, why not just go with sorting by a key?  If
you have some domain which is ordered, but which the builtin <=
doesn't understand, why not just map it into some type which the
builtin recognizes? (For example build a table of integers, where each
integer corresponds to an element in the unsorted sequence.)

You would then need to get at the permutation information which "sort"
generates, but that need not be difficult.  Also, sort had better deal
with sorting strings of some sort, but that need not be difficult
either.

If the mapping from sequence of type X to sequence of builtin type is
simple enough, there is no reason that a compiler couldn't optimize it
out as a distinct step.

I don't see any reason, by the way, to apply sort to a partial order
which is not a complete order.

Raul Rockwell