[Agda] fast DecTotalOrder
Sergei Meshveliani
mechvel at botik.ru
Tue Mar 24 11:29:41 CET 2015
Can people, please, advise me on the following matter?
(which is in fact on Standard library)
For testing the sorting function for performance, I need
(1) the list elements to be from some DecTotalOrder instance
(required by the `sort' function),
(2) _≤?_ to perform fast,
(3) forming a list having as many different elements as needed.
I am going to do this.
a) To implement
stoToDTO : StrictTotalOrder _ _ _→ DecTotalOrder _ _ _
stoToDTO sto =
record{ Carrier = Carrier
; _≈_ = _≈_
; _≤_ = _≤_
; isDecTotalOrder = isDecTotalOrder }
where
open StrictTotalOrder sto using (_≈_; _<_; compare ...)
_≤_ : Rel Carrier _
x ≤ y = x < y ⊎ x ≈ y -- **
...
I expect that DecTotalOrder can be proved for this _≤_ instance.
Right?
b) To use Data.String.StrictTotalOrder,
in which _<_ is by the lexicographic comparison.
I expect that this comparison is fast (O(length string)).
Is it?
c) To apply stoToDTO to Data.String.StrictTotalOrder with
obtaining fast DecTotalOrder for String.
d) To implement suc : String → String as the lexicographically next
string, and to use it for obtaining fast a list xs : List String
with many different elements in xs.
Is this plan correct?
Can the goal be achieved in a simpler way?
First I thought of Bin, but then discovered that _<_ is done there
by conversion to Nat, which is very expensive.
Right?
So, I hope for Data.String.StrictTotalOrder.
Who could advise, please?
Thanks,
------
Sergei
More information about the Agda
mailing list