Agda: Return 空列表的头部和尾部

Question

我正在学习 agda 并在列表上练习以获得更好的理解。现在我正在尝试为列表编写函数。我对如何 return 空列表的头部和尾部感到困惑。这是我的代码：

data list (A : Set) : Set where
[]  : list A
_∷_ : A → list A → list A

Null : {A : Set} → (list A) → Bool
Null [] = true
Null (x ∷ a) = false

tail :  {A : Set} → (list A) → A
tail [] = {!!}
tail (x ∷ []) = x  
tail (x ∷ a) = tail a

head : {A : Set} → (list A) →  A
head [] = {!!}
head (x ∷ a) = x

我发现的一个变通方法是，我 return 一个包含第一个和最后一个成员的列表，而不是 return 第一个和最后一个成员，如下所示：

tail :  {A : Set} → (list A) → (list A)
tail [] = []
tail (x ∷ []) = x ∷ []  
tail (x ∷ a) = tail a

head : {A : Set} → (list A) → (list A)
head [] = []
head (x ∷ a) = (x ∷ [])

但我仍然对如何 return 头值和尾值感到困惑。我该怎么做？

P.S 不是作业。在 class

中领先于此内容

Answer 1

在 Agda 中，函数是全部的：如果你有 head : {A : Set} -> list A -> A，那么它需要在所有列表上定义。但是，对于 head [] 你不能为某种任意类型 A 想出一个元素（假设 head ([] : list Void)...）

问题是您的 head 类型承诺太多。事实上，您可以 return 任何列表的第一个元素都是不正确的；您只能对 non-empty 个列表执行此操作。因此，您需要更改 head 以将 separate proof of non-emptiness, or to take a non-empty list 作为参数：

module SeparateProof where
  open import Data.List
  open import Data.Bool
  open import Data.Unit

  head : {A : Set} → (xs : List A) → {{nonEmpty : T (not (null xs))}} → A
  head [] {{nonEmpty = ()}} -- There's no way to pass a proof of non-emptiness for an empty list!
  head (x ∷ xs) = x

module NonEmptyType where
  open import Data.List.NonEmpty hiding (head)

  head : {A : Set} → List⁺ A → A
  head (x ∷ xs) = x -- This is the only pattern matching a List⁺ A!

Answer 2

这个用词不当，你最后要的不是tail，正确的tail函数你可以看标准库Data\List\Base.agda中的drop:

drop : ∀ {a} {A : Set a} → ℕ → List A → List A
drop zero    xs       = xs
drop (suc n) []       = []
drop (suc n) (x ∷ xs) = drop n xs
--e.g. drop 1
tail : ∀ {a} {A : Set a} → List A → List A
tail []       = []
tail (x ∷ xs) = xs

Agda: Return 空列表的头部和尾部

Agda: Return head and tail of empty list

agda

agda-mode