完整的证明，如果最后一个列表元素不在列表中，那么前置就不会如此

Question

用 Idris 完成类型驱动开发一书的练习 9.1 后，我无法获得完整的证明之一。练习是使 isLast 函数起作用。它应该 return 证明一个值是 List 的最后一个值。它有效，但不幸的是 notLastInTailEqNotLast 不是全部。

data Last : List a -> a -> Type where
     LastOne : Last [value] value
     LastCons : (prf : Last xs value) -> Last (x :: xs) value

lastNotNil : Last [] value -> Void
lastNotNil _ impossible

lastNotEq : (contra : (lastValue = value) -> Void) -> Last [lastValue] value -> Void
lastNotEq contra LastOne = contra Refl
lastNotEq _ (LastCons LastOne) impossible
lastNotEq _ (LastCons (LastCons _)) impossible

notLastInTailEqNotLast : (notLastInTail : Last xs value -> Void) ->
                         Last (y :: xs) value -> Void
notLastInTailEqNotLast notLastInTail LastOne = ?hole
notLastInTailEqNotLast notLastInTail (LastCons prf) = notLastInTail prf


isLast : DecEq a => (xs : List a) -> (value : a) -> Dec (Last xs value)
isLast [] value = No lastNotNil
isLast [lastValue] value = case decEq lastValue value of
  Yes Refl => Yes LastOne
  No contra => No (lastNotEq contra)
isLast (x :: xs) value = case isLast xs value of
  Yes last => Yes (LastCons last)
  No notLastInTail => No (notLastInTailEqNotLast notLastInTail)

如何填写?hole？

我在这里看到了解决方案：https://github.com/edwinb/TypeDD-Samples/blob/master/Chapter9/Exercises/ex_9_1.idr。我了解如何使用 lastNotCons 解决我的问题，并且我可以通过这种方式解决我的问题，但这似乎是一种解决方法。我想提供的证明对我来说似乎微不足道：如果我证明某个元素不是列表中的最后一个元素，那么附加了该列表的另一个列表仍然不会将该元素作为列表中的最后一个元素（即 notLastInTailEqNotLast).

非常感谢您的帮助。

Answer 1

无法证明 notLastInTailEqNotLast，因为它不正确。这是一个反例：0 不是空列表 [] 的最后一个元素，但是如果您将 0 添加到空列表之前，您会突然发现 0 是新列表的最后一个元素。

另一种看待它的方式是当你试图填写 ?hole 时，你的目标是 Void，所以这一定意味着你的上下文应该有矛盾，但是上下文看起来像这样

`--   phTy : Type
      value : phTy
      notLastInTail : Last [] value -> Void
     ---------------------------------------

但是你唯一的矛盾候选者是 notLastInTail。如果你眯着眼睛看它的类型，你会发现它只是你的 lastNotNil 定理，即它并不矛盾。

完整的证明，如果最后一个列表元素不在列表中，那么前置就不会如此

Complete proof that if last list element not in list, prepending will not be making it so

idris