[Agda] withdraw AVL ≈ request?
Sergei Meshveliani
mechvel at botik.ru
Thu Jan 2 15:48:47 CET 2014
People,
Earlier I asked a couple of times about generalizing AVL
(binary tree table) from syntactic equality to a definitional one.
I have thought once more about the subject, and now doubt of whether
this request has sense.
Because to use a generalized ALV Tree, one still needs to have the
following.
(1) To define StrictTotalOrder _≈_ _<_ on A = Key.
(2) Most often it is done by defining a _canonical form_ map on A for
_≈_ and some DecTotalOrder _<_ on canonical forms, where _<_ is
often set only for the purpose of a search by key.
(for any reasonable computation domain it is really possible to define
(1) and (2), if one really cares for AVL).
And it occurs that (1) and (2) give a map to a key domain Key' where
Key' can be used with _≡_ and _<_.
So, to use AVL of lib-0.7, one needs to add to one's `classes' such
operations as canonical-form-as-key, _<_-as-key, key-StrictTotalOrder,
and to define them for each appropriate class instance.
For example, having such for A and B, one can define such for
A \times B, and for List A.
Probably the above AVL generalization will not make it any easier the
approach with (1) and (2) and defining instances.
There remains a certain point.
Having a canonical map to Key', one could think of using some default
built-in (_>_ , sto : StrictTotalOrder _≡_ _<_),
because it usually needs effort to invent this _<_.
As I recall, the Haskell library has such (do not recall of whether it
is on Standard).
The question is: whether Agda library could have such.
Regards,
------
Sergei
More information about the Agda
mailing list