在 Agda 中使用字符串作为键进行映射？

Question

我在弄清楚如何在 Agda 中正确制作带有字符串键的地图时遇到了一些问题。我有以下内容：

import Data.AVL.IndexedMap

Var = String

data Type where -- ...

alwaysType : Var -> Set
alwaysType _ = Type

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

这给出了错误：

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

地图模块的正确打开方式是什么？

Answer 1

Data.AVL.IndexedMap 模块用于（有限）映射，其中键和值有一系列类型，并且与给定键关联的值与值共享索引。

这不是您想要的，因为您希望所有密钥都是 String。所以只需使用 Data.AVL （即带有非索引键的版本）：

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)

不幸的是，这仍然没有进行类型检查：

.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

这是因为 Data.String.strictTotalOrder 使用逐点相等（在构成 String 的 Char 的 ℕ 值的列表上），并且 Data.AVL 要求命题相等。因此，完全相同的示例适用于 ℕ 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)

所以下一步需要将 StrictTotalOrder.isStrictTotalOrder Data.String.strictTotalOrder 转换为 IsStrictTotalOrder (_≡_ {A = String}) _ 类型的东西。我暂时把它留给其他人，但我很乐意稍后再研究，如果我有时间，如果你不能让它工作，也没有其他人接手它。

编辑添加：这是一种（可能过于复杂的）将标准库中的 String 的 StrictTotalOrder 转换为某种东西的方法使用命题相等：

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

Answer 2

请注意，标准库的 Data.AVL 已更新为接受不基于命题相等性的严格总顺序。

如今它很简单：

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

在 Agda 中使用字符串作为键进行映射？

Map with Strings as Keys in Agda?

types

functional-programming

module

agda

dependent-type