[Agda] fast DecTotalOrder
Sergei Meshveliani
mechvel at botik.ru
Tue Mar 24 16:26:24 CET 2015
On Tue, 2015-03-24 at 16:00 +0100, Nils Anders Danielsson wrote:
> On 2015-03-24 14:30, Sergei Meshveliani wrote:
> > On Tue, 2015-03-24 at 14:05 +0100, Nils Anders Danielsson wrote:
> >> _<_ is used in the specification of compare:
> >>
> >> _<_ : Bin → Bin → Set
> >> compare : Trichotomous _≡_ _<_
> >>
> >
> >
> > This looks like a pitfall.
> > Probably, there are many applications which use a generic
> > StrictTotalOrder._<_.
> > And as soon as A = Bin is substituted, their performance cost will
> > explode unexpectedly.
>
> Why? Do you plan to evaluate the proofs? Or do you worry about the space
> consumed by unevaluated thunks?
>
Sorry, I have forgotten that in my example, _<_ and _≤?_ are used
differently.
Probably, _<_ and _≤_ are only for proofs.
A false alarm.
In my example, it is essential that the second part for the proof for
`sort' is not evaluated (unless the performance cost explodes).
Sometimes it may be good to evaluate a proof. But probably I would not
rely in such a case that _<_ is fast. Otherwise it would be generally
too difficult to set proofs.
Regards,
------
Sergei
More information about the Agda
mailing list