Vec: filter: 我不确定是否应该有构造函数 []

Question

我正在尝试为 Vec 定义一个过滤器函数：

vecFilter : ∀ {P : Pred A p} → Decidable P → ∀ {n m : ℕ} → Vec A (m + n) → Vec A n
vecFilter P? [] = []
vecFilter P? (x ∷ xs) with does (P? x)
... | false = vecFilter P? xs
... | true  = x ∷ vecFilter P? xs

我基于 Data.List filter 以及 Data.Vec count.

我收到以下错误消息：

I'm not sure if there should be a case for the constructor [],
because I get stuck when trying to solve the following unification
problems (inferred index ≟ expected index):
  ℕ.zero ≟ n + m
when checking that the pattern [] has type Vec A (n + m)

我想知道这是否与我使用 Vec A (n + m) 的事实有关。

Answer 1

我刚刚注意到 filter 已经为 Vec Data.Vec 实现了。我在 Data.Vec.Base

中搜索

Answer 2

您建议的类型 filter 非常慷慨：

vecFilter : ∀ {P : Pred A p} → Decidable P → ∀ {n m : ℕ} → Vec A (m + n) → Vec A n

它声称对于任何可判定谓词 P 和 任何一对自然数 n 和 m，你可以转换一个m + n 个元素的向量到 n 个元素的向量。

然而，这显然不是真的；例如，如果我选择 P 作为 const ⊤，n 作为 0，m 作为 1，则需要您的过滤函数从 one-element 向量，即使谓词必然适用于那个元素。

那我们能做什么呢？选择删除多少个元素 (m) 必须由您的函数进行；换句话说，它必须以某种方式存在量化。实际的做法是说 vecFilter 可以作用于任意长度的任意向量，然后 return 删除元素个数的依赖对，剩下的元素：

vecFilter : ∀ {P : Pred A p} → Decidable P → ∀ {n : ℕ} → Vec A n → Σ ℕ λ m → Vec A (n ∸ m)

当然，标准库中的实际实现要好一些，它使用唯一表示长度差异（而 n ∸ m 允许 10 ∸ 10000 之类的东西表示空结果）。

Vec: filter: 我不确定是否应该有构造函数 []

Vec: filter: I'm not sure if there should be a case for the constructor []

agda