在 Haskell 中实现 Lambda 演算的模式匹配
Pattern matching implementing Lambda calculus in Haskell
我想编写一个函数来收集已在 lambda 演算术语中使用的变量名称，既作为变量又作为 Lambda 抽象。
例如在代码中我会得到以下输出：
*Main> used example
["a","b","x","y"]
我想 return 将它们排列在有序列表中。我想我可以使用模式匹配和通配符来实现，这可能吗？
import Data.Char
import Data.List
type Var = String
data Term =
Variable Var
| Lambda Var Term
| Apply Term Term
example :: Term
example = Lambda "a" (Lambda "x" (Apply (Apply (Lambda "y" (Variable "a"))
(Variable "x"))
(Variable "b")))
-- I'll use this function to merge two ordered lists together:
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
| x == y = x : merge xs ys
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
used :: Term -> [Var]
used [] = []
used Variable_ = _
used Lambda_ = _
used Apply_ = _
这显然是不正确的。
如何收集变量名并将它们添加到列表中？如果模式匹配和通配符不正确，请您建议我该怎么做？
所以used是一个函数Term -> [Var]。因此，要以模式匹配样式编写 used，我们需要为每种不同的方式创建案例 Term。查看 Term 的定义，我们发现有 3 种方法可以成为 Term：成为变量、lambda 或应用。特别是作为一个空列表 ([]) 并不是成为 Term 的一种方式，因此应该删除这种情况。
接下来让我们看看模式匹配的语法。它应该如下所示：
used :: Term -> [Var]
used (Variable var) = ...
used (Lambda var term) = ...
used (Apply term1 term2) = ...
注意每组数据构造函数和参数周围的括号。另请注意，Haskell 中的变量必须以小写字符开头。最后请注意，我们实际上还没有为 used 编写任何案例主体。以上实际上无效 Haskell.
让我们来看看如何填写这些案例的所有右侧。当我们这样做时，请记住 used 意味着 return 一个 Var 的有序列表，没有重复。其中大部分未以 used.
的类型捕获
Variable案例：
used (Variable var) = ...
所以这里的右边必须是 Var 的列表。检查 Term 和 Variable 的声明，我们看到 var 必须是 Var。因此，真正实现的唯一选择是：
used (Varable var) = [var]
Lambda案例
used (Lambda var term) = ...
所以再次检查 Term 的类型声明，我们看到 var 是 Var 而 term 是 Term。也许这就是我们使用这些变量名称的原因 ;)。所以有些变量出现在var中，有些变量出现在term中。如果我们知道所有这些变量，我们可以将这些结果与 merge 放在一起。对于 var 我们可以做与 Variable 情况相同的事情。对于 term，我们需要一种方法将 Term 转换为变量或变量列表。幸运的是我们有这样的方法。这是我们当前正在定义的函数：used！所以我们可以把这种情况写成：
used (Lambda var term) = merge [var] (used term)
使用 merge 将单例列表合并到另一个列表中可能看起来有点傻，但我们需要保持结果的有序性，而 merge 是我们的锤子，所以我们把这个问题成钉子。
Apply案例
使用与上述相同的想法，此案例将很快完成。我们有
used (Apply term1 term2) = ...
term1 和 term2 是 Term 的。我们将使用 used 从每个变量中提取变量，并使用 merge.
将它们合并在一起
used (Apply term1 term2) = merge (used term1) (used term2)
总的来说，这给出了 used:
的实现
used :: Term -> [Var]
used (Variable var) = [var]
used (Lambda var term) = merge [var] (used term)
used (Apply term1 term2) = merge (used term1) (used term2)
和
*Main> used example
["a","b","x","y"]
随心所欲。
我想编写一个函数来收集已在 lambda 演算术语中使用的变量名称，既作为变量又作为 Lambda 抽象。
例如在代码中我会得到以下输出：
*Main> used example
["a","b","x","y"]
我想 return 将它们排列在有序列表中。我想我可以使用模式匹配和通配符来实现，这可能吗？
import Data.Char
import Data.List
type Var = String
data Term =
Variable Var
| Lambda Var Term
| Apply Term Term
example :: Term
example = Lambda "a" (Lambda "x" (Apply (Apply (Lambda "y" (Variable "a"))
(Variable "x"))
(Variable "b")))
-- I'll use this function to merge two ordered lists together:
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
| x == y = x : merge xs ys
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
used :: Term -> [Var]
used [] = []
used Variable_ = _
used Lambda_ = _
used Apply_ = _
这显然是不正确的。
如何收集变量名并将它们添加到列表中？如果模式匹配和通配符不正确，请您建议我该怎么做？
所以used是一个函数Term -> [Var]。因此，要以模式匹配样式编写 used，我们需要为每种不同的方式创建案例 Term。查看 Term 的定义，我们发现有 3 种方法可以成为 Term：成为变量、lambda 或应用。特别是作为一个空列表 ([]) 并不是成为 Term 的一种方式，因此应该删除这种情况。
接下来让我们看看模式匹配的语法。它应该如下所示：
used :: Term -> [Var]
used (Variable var) = ...
used (Lambda var term) = ...
used (Apply term1 term2) = ...
注意每组数据构造函数和参数周围的括号。另请注意，Haskell 中的变量必须以小写字符开头。最后请注意，我们实际上还没有为 used 编写任何案例主体。以上实际上无效 Haskell.
让我们来看看如何填写这些案例的所有右侧。当我们这样做时，请记住 used 意味着 return 一个 Var 的有序列表，没有重复。其中大部分未以 used.
Variable案例：
used (Variable var) = ...
所以这里的右边必须是 Var 的列表。检查 Term 和 Variable 的声明，我们看到 var 必须是 Var。因此，真正实现的唯一选择是：
used (Varable var) = [var]
Lambda案例
used (Lambda var term) = ...
所以再次检查 Term 的类型声明，我们看到 var 是 Var 而 term 是 Term。也许这就是我们使用这些变量名称的原因 ;)。所以有些变量出现在var中，有些变量出现在term中。如果我们知道所有这些变量，我们可以将这些结果与 merge 放在一起。对于 var 我们可以做与 Variable 情况相同的事情。对于 term，我们需要一种方法将 Term 转换为变量或变量列表。幸运的是我们有这样的方法。这是我们当前正在定义的函数：used！所以我们可以把这种情况写成：
used (Lambda var term) = merge [var] (used term)
使用 merge 将单例列表合并到另一个列表中可能看起来有点傻，但我们需要保持结果的有序性，而 merge 是我们的锤子，所以我们把这个问题成钉子。
Apply案例
使用与上述相同的想法，此案例将很快完成。我们有
used (Apply term1 term2) = ...
term1 和 term2 是 Term 的。我们将使用 used 从每个变量中提取变量，并使用 merge.
used (Apply term1 term2) = merge (used term1) (used term2)
总的来说，这给出了 used:
used :: Term -> [Var]
used (Variable var) = [var]
used (Lambda var term) = merge [var] (used term)
used (Apply term1 term2) = merge (used term1) (used term2)
和
*Main> used example
["a","b","x","y"]
随心所欲。