使用列表串联的数据类型索引的问题

Question

我在对一个定理进行形式化时遇到了一个棘手的问题，该定理使用的数据类型具有一些构造函数，其索引具有列表串联。当我尝试使用 emacs 模式进行大小写拆分时，Agda returns 出现以下错误信息：

I'm not sure if there should be a case for the constructor
o-success, because I get stuck when trying to solve the following
unification problems (inferred index ≟ expected index):
  e₁ o e'' , x₁ ++ x'' ++ y₁ ≟ e o e' , x ++ x' ++ y
  suc (n₂ + n'') , x₁ ++ x'' ≟ m' , p''
when checking that the expression ? has type
suc (.n₁ + .n') == .m' × .x ++ .x' == p'

由于代码行数较多，我将其放在以下要点中：

https://gist.github.com/rodrigogribeiro/976b3d5cc82c970314c2

如有任何提示，我们将不胜感激。

最佳，

Answer 1

有一个类似的question。

但是你想统一 xs1 ++ xs2 ++ xs3 和 ys1 ++ ys2 ++ ys3，但是 _++_ 不是构造函数——它是一个函数，它不是单射的。考虑这个简化的例子：

data Bar {A : Set} : List A -> Set where
  bar : ∀ xs {ys} -> Bar (xs ++ ys)

ex : ∀ {A} {zs : List A} -> Bar zs -> Bar zs -> List A
ex (bar xs) b = {!!}

b 是 Bar (xs ++ .ys) 类型，但是 b 不一定等于 bar .xs，所以你不能像这样进行模式匹配。这里有两个 Bar ，它们具有相同的类型但不同的值：

ok : ∃₂ λ (b1 b2 : Bar (tt ∷ [])) -> b1 ≢ b2
ok = bar [] , bar (tt ∷ []) , λ ()

这是因为 xs1 ++ xs2 ≡ ys1 ++ ys2 通常并不意味着 xs1 ≡ ys1 × xs2 ≡ ys2。

但是可以概括索引。您可以使用 Vitus 在上面 link 中描述的技术，或者您可以使用这个简单的组合器，它会忘记索引：

generalize : ∀ {α β} {A : Set α} (B : A -> Set β) {x : A} -> B x -> ∃ B
generalize B y = , y

例如

ex : ∀ {A} {zs : List A} -> Bar zs -> Bar zs -> List A
ex {A} (bar xs) b with generalize Bar b
... | ._ , bar ys = xs ++ ys

毕竟，你确定你的引理是真的吗？

更新

先说几点。

您的 empty 案例状态

empty : forall x -> G :: (emp , x) => (1 , x)

empty 解析器解析整个字符串。应该是

empty : forall x -> G :: (emp , x) => (1 , [])

如论文所述。

您对 o-fail1 的定义包含此部分：

(n , fail ∷ o)

但是 fail 失败了，所以它应该是 (n , fail ∷ [])。使用这种表示，您可能需要 A 上的可判定相等性来完成引理，并且证明会很脏。表示可能会失败的东西的干净和惯用的方法是将它包装在 Maybe monad 中，所以这是我对 _::_=>_:

的定义

data _::_=>_ {n} (G : Con n) : Foo n × List A -> Nat × Maybe (List A) -> Set where
  empty       : ∀ {x}     -> G :: emp   ,  x      => 1 , just []
  sym-success : ∀ {a x}   -> G :: sym a , (a ∷ x) => 1 , just (a ∷ [])
  sym-failure : ∀ {a b x} -> ¬ (a == b) -> G :: sym a , b ∷ x => 1 , nothing
  var         : ∀ {x m o} {v : Fin (suc n)}
              -> G :: lookup v G , x => m , o -> G :: var v , x => suc m , o
  o-success : ∀ {e e' x x' y n n'}
            -> G :: e      , x ++ x' ++ y => n            , just x
            -> G :: e'     ,      x' ++ y => n'           , just x'
            -> G :: e o e' , x ++ x' ++ y => suc (n + n') , just (x ++ x')
  o-fail1   : ∀ {e e' x x' y n}
            -> G :: e      , x ++ x' ++ y => n     , nothing
            -> G :: e o e' , x ++ x' ++ y => suc n , nothing
  o-fail2   : ∀ {e e' x x' y n n'}
            -> G :: e      , x ++ x' ++ y => n            , just x
            -> G :: e'     ,      x' ++ y => n'           , nothing
            -> G :: e o e' , x ++ x' ++ y => suc (n + n') , nothing

这里是 lemma:

postulate
  cut : ∀ {α} {A : Set α} -> ∀ xs {ys zs : List A} -> xs ++ ys == xs ++ zs -> ys == zs

mutual
  aux : ∀ {n} {G : Con n} {e e' z x x' y n n' m' p'}
      -> z == x ++ x' ++ y
      -> G :: e      , z       => n  , just x
      -> G :: e'     , x' ++ y => n' , just x'
      -> G :: e o e' , z       => m' , p'
      -> suc (n + n') == m' × just (x ++ x') == p'
  aux {x = x} {x'} {n = n} {n'} r pr1 pr2 (o-success {x = x''} pr3 pr4) with x | n | lemma pr1 pr3
  ... | ._ | ._ | refl , refl rewrite cut x'' r with x' | n' | lemma pr2 pr4
  ... | ._ | ._ | refl , refl = refl , refl
  aux ...

  lemma : ∀ {n m m'} {G : Con n} {f x p p'}
        -> G :: f , x => m , p -> G :: f , x => m' , p' -> m == m' × p == p'
  lemma (o-success pr1 pr2)  pr3            = aux refl pr1 pr2 pr3
  lemma ...

证明过程如下：

我们概括了lemma's pr3 in an auxiliary function as in the Vitus'答案的类型。现在可以在 pr3.
我们证明，lemma's pr3 中的第一个解析器（在 aux 中也称为 pr3）产生与 pr1 相同的输出.
经过一些重写，我们证明 lemma 的 pr3 中的第二个解析器（在 aux 中称为 pr4）产生与 pr2.
并且由于 pr1 和 pr3 产生相同的输出，并且 pr2 和 pr4 产生相同的输出，因此 o-success pr1 pr2 和 o-success pr3 pr4 产生相同的输出，所以我们输入 refl , refl.

code。我没有证明 o-fail1 和 o-fail2 的情况，但它们应该是相似的。

更新

样板文件的数量可以减少

修复 fail 个案例的定义，其中包含冗余信息。
返回 Maybe (List A) 而不是 Nat × Maybe (List A)。如果需要，您可以递归计算此 Nat。
使用 inspect 习语代替辅助功能。

我认为没有更简单的解决方案。 code.

使用列表串联的数据类型索引的问题

Problems on data type indices that uses list concatenation

agda