使用 Idris 实现 isLast：不在尾部

Question

我正在做 Type-Driven Development with Idris 的第 9.1 节中的练习 2，但我不知道如何填补最后一个洞（请参阅 notInTail, 下面）。

我已经阅读了的答案，但我卡在了另一个地方。

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

notInNil : Last [] value -> Void
notInNil LastOne impossible
notInNil (LastCons _) impossible

notLast : (notHere : (x = value) -> Void) -> Last [x] value -> Void
notLast prf LastOne = absurd (prf Refl)
notLast prf (LastCons _) impossible

notInTail : (notThere : Last xs value -> Void) -> Last (x :: xs) value -> Void
notInTail notThere LastOne = ?hole
notInTail notThere (LastCons prf) = notThere prf

isLast : DecEq a => (xs : List a) -> (value : a) -> Dec (Last xs value)
isLast [] value = No notInNil
isLast (x :: []) value = case decEq x value of
                              Yes Refl => Yes LastOne
                              No notHere => No (notLast notHere)
isLast (_ :: xs) value = case isLast xs value of
                              Yes prf => Yes (LastCons prf)
                              No notThere => No (notInTail notThere)

这是 Idris 的报告：

- + Main.hole [P]
 `--       phTy : Type
          value : phTy
       notThere : Last [] value -> Void
     -----------------------------------
      Main.hole : Void

Answer 1

我认为您无法证明所写的 notInTail，因为它不适用于空列表。但是它确实适用于 non-empty 个列表：

notInTail : (c : Last (y :: ys) value -> Void) -> Last (x :: (y :: ys)) value -> Void
notInTail c (LastCons prf) = c prf

在 isLast 的第三种情况下，输入列表的尾部必须是 non-empty，但您没有指定它。如果你这样做，那么你可以申请 notInTail:

isLast (x :: (y :: xs)) value = case isLast (y :: xs) value of
                                     Yes prf => Yes (LastCons prf)
                                     No c => No (notInTail c)

使用 Idris 实现 isLast：不在尾部

Implementing isLast with Idris: not in tail

idris