[Agda] finite map

Sergei Meshveliani mechvel at botik.ru
Tue Dec 17 09:53:42 CET 2013


On Sat, 2013-12-14 at 20:57 +0400, Sergei Meshveliani wrote:
> People,
> I have   A : Setoid α α=,  aC = Setoid.Carrier A,  B : Setoid β β=,
>          bC = Setoid.Carrier B,
> 
> and need to operate with finite maps  f : aC → bC :
> 
> membership, lookup, insertion, union, equality.
> O(n) lookup/insert  is sufficient, so far.

I consider implementing  AssociationList,
like AssocList in the Haskell library, only with some proofs.

Has the Agda standard library such? 


> Need I to add a number  i : ℕ,  to make pairs  (x , i) : aC × ℕ
> compared _<_  by  i,  and to use  AVL  over the TotalOrder key domain of
> aC × ℕ
> ?

The idea was that _≡_ on  ℕ × aC  to support operating with  _≈_ on aC
(as Data.AVL relies on _≡_).
But probably, this is an error.

Thanks,

------
Sergei




More information about the Agda mailing list