CODEWITHSUNDEEP
agda
123omnomnom
123omnomnom

Reputation: 309

Proving two dependent (AVL tree key-value) pairs equal

The standard library's AVL tree implementation uses dependent pairs to store key-value pairs. I have two such pairs whose keys (k and k′) I have shown to be equal (k≡k′). They also contain the same value (v). I'd like to prove that the pairs are equal. Here's the goal:

open import Agda.Primitive

open import Data.Nat
open import Data.Nat.Properties
open import Data.Product
open import Relation.Binary.PropositionalEquality

open import Data.AVL.Indexed <-strictTotalOrder

module Repro (ℓ : Level) (V : Value ℓ) where

Val = Value.family V
V≈ = Value.respects V

proof : (k k′ : ℕ) → (v : Val k) → (k≡k′ : k ≡ k′) → (k , v) ≡ (k′ , V≈ k≡k′ v)
proof k k′ v k≡k′ = {!!}

I tried rewriting with k≡k′, which turns k on the LHS into k′ and k≡k′ on the RHS into refl. That's where I get stuck. I feel like I'm missing something obvious, as this seems a pretty basic thing to do.

(As an exercise, I'm trying to prove the standard library's AVL tree insertion correct. Hence my recent obsession with its AVL tree code.)

Update

Hmm. Maybe this isn't as trivial as I thought, at least without knowing more about V. After all, what I currently know is that:

What I don't know at this point is that V≈ refl is the identity function, which seems to be what I'd need to do my proof.

Update II

If, for example, I knew that V≈ was actually subst Val, then my proof would be:

proof′ : (k k′ : ℕ) → (v : Val k) → (k≡k′ : k ≡ k′) → (k , v) ≡ (k′ , subst Val k≡k′ v)
proof′ k k′ v k≡k′ rewrite k≡k′ = cong (k′ ,_) refl

So, I guess my question ultimately is:

Update III

I am providing more context in response to MrO's comment. Instead of stripping down my actual proof, I'll provide something even simpler. Let's prove a special case of AVL tree insertion, which leads to the same problem that I'm facing in the general case.

Let's prove that inserting a value v for key k into an empty tree and then looking up the value for key k yields the value v that we inserted.

Let's get set up:

open import Agda.Primitive using (Level)
open import Data.Maybe using (just)
open import Data.Nat using (ℕ)
open import Data.Nat.Properties using (<-strictTotalOrder ; <-cmp)
open import Data.Product using (proj₂)
open import Function using () renaming (const to constᶠ)
open import Relation.Binary using (tri< ; tri≈ ; tri>)
open import Relation.Binary.PropositionalEquality using (_≡_ ; refl )
open import Relation.Nullary.Negation using (contradiction)

open import Data.AVL.Indexed <-strictTotalOrder

module Simple {ℓ : Level} (V : Value ℓ) where

private
  Val = Value.family V
  V≈  = Value.respects V

Now, a function to create an empty tree:

make-empty : ∀ {l u} → l <⁺ u → Tree V l u 0
make-empty = leaf

And the proof:

proof : ∀ {l u} (k : ℕ) (v : Val k) (l<u : l <⁺ u) (l<k<u : l < k < u) →
  lookup k (proj₂ (insertWith k (constᶠ v) (make-empty l<u) l<k<u)) l<k<u ≡ just v

proof k v l<u l<k<u with <-cmp k k
... | tri< _ p _ = contradiction refl p
... | tri> _ p _ = contradiction refl p
... | tri≈ _ p _ rewrite p = {!!}

The goal that I'm trying to fill in is just (V≈ refl v) ≡ just v.

Upvotes: 0

Views: 187

Answers (1)

MrO
MrO

Reputation: 1347

You could postulate, or take as a module parameter, the fact that V≈ leaves the value unchanged, as follows:

postulate lemma : ∀ {k k′} {v : Val k} → (k≡k′ : k ≡ k′) → v ≡ subst _ (sym k≡k′) (V≈ k≡k′ v)

After that, your proof becomes:

proof : (k k′ : ℕ) → (v : Val k) → (k≡k′ : k ≡ k′) → (k , v) ≡ (k′ , V≈ k≡k′ v) 
proof k ._ _ refl = cong (k ,_) (lemma refl)

Upvotes: 1

Related Questions