Map with Strings as Keys in Agda?

Question

I'm having some trouble figuring out how to properly make a Map with String keys in Agda. I've got the following:

import Data.AVL.IndexedMap

Var = String

data Type where -- ...

alwaysType : Var -> Set
alwaysType _ = Type

open Data.AVL.IndexedMap alwaysType (StrictTotalOrder.isStrictTotalOrder Data.String.strictTotalOrder) 

This gives the error:

String != Σ String _Key_90 of type Set
when checking that the expression
StrictTotalOrder.isStrictTotalOrder strictTotalOrder has type
Relation.Binary.IsStrictTotalOrder .Agda.Builtin.Equality._≡_
__<__91

What is the proper way to open the Map module?

Rapallo

I'm fine if you correct the code in my answer, but changing it the question seems like it would be likely to change the error I'm getting – Rapallo

No, the error remains the same, since it's because your key type String is not of the right kind Index -> Set. – Untutored

Other relevant answers: https://mcmap.net/q/1351768/-agda-39-s-standard-library-data-avl-sets-containing-data-string-as-values, https://mcmap.net/q/1470254/-lexicographic-ordering-of-pairs-lists-in-agda-using-the-standard-library – Untutored

Possible duplicate of Agda's standard library Data.AVL.Sets containing Data.String as values – Rapallo

Answer 1

The Data.AVL.IndexedMap module is for (finite) maps where there is a family of types for the keys and the values, and the value associated with a given key shares the index with the value.

This is not what you want here, since you want all your keys to be Strings. So just use Data.AVL (i.e. the version with non-indexed keys):

open import Data.String using (String)
open import Function using (const)

Key = String

postulate
  Value : Set

open import Relation.Binary using (StrictTotalOrder)
open import Data.AVL (const Value) (StrictTotalOrder.isStrictTotalOrder Data.String.strictTotalOrder)

Unfortunately, this still doesn't typecheck:

.Relation.Binary.List.Pointwise.Rel
(StrictTotalOrder._≈_ .Data.Char.strictTotalOrder)
(Data.String.toList x) (Data.String.toList x₁)
!= x .Agda.Builtin.Equality.≡ x₁ of type Set
when checking that the expression
StrictTotalOrder.isStrictTotalOrder Data.String.strictTotalOrder
has type IsStrictTotalOrder .Agda.Builtin.Equality._≡_ __<__10

That's because Data.String.strictTotalOrder uses pointwise equality (over the list of ℕ values of the Chars that make up the String), and Data.AVL requires propositional equality. So the exact same example would work with, e.g., ℕ keys:

open import Data.Nat using (ℕ)
open import Function using (const)

Key = ℕ

postulate
  Value : Set

import Data.Nat.Properties
open import Relation.Binary using (StrictTotalOrder)

open import Data.AVL (const Value) (StrictTotalOrder.isStrictTotalOrder Data.Nat.Properties.strictTotalOrder)

So the next step needs to be to transform StrictTotalOrder.isStrictTotalOrder Data.String.strictTotalOrder into something of type IsStrictTotalOrder (_≡_ {A = String}) _. I'll leave that to someone else for now, but I'm happy to look into it later, when I have the time, if you can't get it working and noone else picks it up either.

EDITED TO ADD: Here's a (possibly horribly over-complicated) way of turning that StrictTotalOrder for Strings from the standard lib into something that uses propositional equality:

open import Function using (const; _∘_; _on_)
open import Relation.Binary

open import Data.String
  using (String; toList∘fromList; fromList∘toList)
  renaming (toList to stringToList; fromList to stringFromList)

open import Relation.Binary.List.Pointwise as Pointwise
open import Relation.Binary.PropositionalEquality as P hiding (trans)
open import Data.Char.Base renaming (toNat to charToNat)

STO : StrictTotalOrder _ _ _
STO = record
  { Carrier = String
  ; _≈_ = _≡_
  ; _<_ = _<_
  ; isStrictTotalOrder = record
    { isEquivalence = P.isEquivalence
    ; trans = λ {x} {y} {z} → trans {x} {y} {z}
    ; compare = compare
    }
  }
  where
    open StrictTotalOrder Data.String.strictTotalOrder 
      renaming (isEquivalence to string-isEquivalence; compare to string-compare)

    -- It feels like this should be defined somewhere in the
    -- standard library, but I can't find it...
    primCharToNat-inj : ∀ {x y} → primCharToNat x ≡ primCharToNat y → x ≡ y
    primCharToNat-inj _ = trustMe
      where
        open import Relation.Binary.PropositionalEquality.TrustMe

    open import Data.List
    lem : ∀ {xs ys} → Pointwise.Rel (_≡_ on primCharToNat) xs ys → xs ≡ ys
    lem [] = P.refl
    lem {x ∷ xs} {y ∷ ys} (x∼y ∷ p) with primCharToNat-inj {x} {y} x∼y
    lem {x ∷ xs} {_ ∷ ys} (x∼y ∷ p) | P.refl = cong _ (lem p)

    ≡-from-≈ : {s s′ : String} → s ≈ s′ → s ≡ s′
    ≡-from-≈ {s} {s′} p = begin
         s ≡⟨ sym (fromList∘toList _) ⟩
         stringFromList (stringToList s) ≡⟨ cong stringFromList (lem p) ⟩
         stringFromList (stringToList s′) ≡⟨ fromList∘toList _ ⟩
         s′ ∎
      where
        open P.≡-Reasoning

    ≈-from-≡ : {s s′ : String} → s ≡ s′ → s ≈ s′
    ≈-from-≡ {s} {_} refl = string-refl {s}
      where
        open IsEquivalence string-isEquivalence renaming (refl to string-refl) using ()

    compare : (x y : String) → Tri (x < y) (x ≡ y) _
    compare x y with string-compare x y
    compare x y | tri< a ¬b ¬c = tri< a (¬b ∘ ≈-from-≡) ¬c
    compare x y | tri≈ ¬a b ¬c = tri≈ ¬a (≡-from-≈ b) ¬c
    compare x y | tri> ¬a ¬b c = tri> ¬a (¬b ∘ ≈-from-≡) c

Untutored

Answer 2

Note that the standard library's Data.AVL has been updated to accept strict total orders not based on propositional equality.

These days it is as simple as:

open import Data.String.Properties
open import Data.AVL strictTotalOrder

Gibbsite