定义中的平等（可判定的平等？例如替换列表中的元素）

Question

我正在尝试学习 lean 并想定义一个替换函数，它采用两个元素 x 和 y 并将每次出现的 x 替换为 y 在给定列表中。

我试着这样定义它：

def replace {α : Type}: α -> α -> list α -> list α
| a b [] := []
| a b (x::xs) := (if a = x then b else x) :: replace a b xs

这给了我以下错误：

error: failed to synthesize type class instance for
α : Type,
replace : α → α → list α → list α,
a b x : α,
xs : list α
⊢ decidable (a = x)

我的问题是我不能对类型 α 使用等式，所以我想我需要限制 α 为某种类型class 其中平等是可判定的（就像我在 Haskell 中所做的那样）。我该怎么做？

我目前的解决方法是将相等函数作为参数：

def replace {α : Type}: (α -> α -> bool) -> α -> α -> list α -> list α
| eq a b [] := []
| eq a b (x::xs) := (if eq a x then b else x) :: replace eq a b xs

Answer 1

您可以将 α 的可判定等式作为类型 class 参数，如下所示：

def replace {α : Type} [decidable_eq α] : α -> α -> list α -> list α
| a b [] := []
| a b (x::xs) := (if a = x then b else x) :: replace a b xs

#eval replace 2 3 [2, 2, 5, 6, 3, 2]

方括号表示类型class的实例应该由类型class解析推断。

定义中的平等（可判定的平等？例如替换列表中的元素）

Equality in definitions (decidable equality? e.g. replace elements in list)

typeclass

lean