test: Sort.pig now has insertion sort! This file defines insertion sort for the natural numbers in a way which guarantees ordered output. (I know, need the permutation bit...)
test: Sort.pig now has insertion sort!
This file defines insertion sort for the natural numbers in a way which
guarantees ordered output. (I know, need the permutation bit...)

A bespoke eliminator, owotoNat, compares values and extends the context
with an inequality "one way or the other".

The natural numbers are extended with artificial bottom and top, and
these are used as loose bounds for ordered lists. Ordered lists are
defined directly, in Presbyterian style. This makes things a bit of a
mess and means I end up doing a rather slow iinduction instead of a nice
tidy split.

The insertion function is almost normal. All of the proofs are handled
implicitly!

It even works on an example, before the heat death of the universe!

Some of the automatics are overcooked, some are undercooked, but basically,
this is Epigram programming!

kwangkim/pigment,kwangkim/pigment,brixen/Epigram,kwangkim/pigment