评估值相等时发生类型不匹配

Question

我是 Idris 的初学者，正在尝试使代码有效。

Could you let me know the better place for noob questions on Idris?

filter : (elem -> Bool) -> Vect len elem -> (p: (Fin len) ** Vect (finToNat p) elem)
filter {len=S l} p xs = ((FZ {k=l}) ** [])
filter {len=S l} p (x::xs) =
  let (a ** tail) = filter {len=l} p xs
   in if p x then
        ((FS a) ** x::tail)
      else
        ((weaken a) ** tail)

我写了另一个 filter 还不能通过类型检查。

这个新的 filter 类型意味着过滤后的向量不能比原始向量长。

然而，伊德里斯说

...
Specifically:
                Type mismatch between
                        finToNat a
                and
                        finToNat (weaken a)

我们知道这两个词总是具有相同的值。

我如何描述事实并让 Idris 同意？

Answer 1

你必须证明 finToNat a = finToNat (weaken a)。 tail 的类型为 Vect (finToNat a) elem，但最后一行的第二个组件需要 Vect (finToNat (weaken a)) elem，因为您在第一对组件中写了 weaken a。

lemma : {n : _} -> (a : Fin n) -> finToNat (weaken a) = finToNat a
lemma FZ     = Refl
lemma (FS x) = rewrite lemma x in Refl

filter : (elem -> Bool) -> Vect len elem -> (p: (Fin len) ** Vect (finToNat p) elem)
filter {len=S l} p xs = ((FZ {k=l}) ** [])
filter {len=S l} p (x::xs) =
  let (a ** tail) = Main.filter {len=l} p xs
  in if p x then
       ((FS a) ** x::tail)
     else
       (weaken a ** (rewrite lemma a in tail))

评估值相等时发生类型不匹配

type mismatch occurs while the evaluated values are equal

functional-programming

dependent-type

idris