haskell - 纯 Lambda 微积分 - 和函数

Question

我目前正在学习 Haskell，并且还在大学参加关于函数式编程的相当理论的讲座。

我知道这纯粹是理论/学术问题，但是我很感兴趣如何用纯 lambda 演算(即没有定义任何常量)简单地表达不同的简单函数。

我的一些讲座 Material 定义了 bool 值，例如:

True = \xy.x
False = \xy.y

(\表示 lambda 符号)

如果它们像这些选择器函数一样定义，则 if 条件可以很容易地定义为:

If = \x.x

现在，我正在尝试为逻辑“和”函数想出一些简短的形式。我的第一个猜测是:

and = \xy.{(If x)[(If y) True False] False}

所以基本上这个 lambda 函数将接收 2 个参数 u v，其中两个参数都必须像 True/False 一样输入。如果我对逻辑表的所有 4 种组合进行各种 beta 缩减，我会收到正确的结果。

不过这个函数看起来有点难看，我正在考虑让它更优雅。这里有什么建议吗？

Answer 1

我们可以对您的答案进行简化以获得更简洁的答案。

首先是一些热身。显然 IF x ==> x , 和 TRUE TRUE FALSE ==> TRUE和 FALSE TRUE FALSE ==> FALSE如果 x是 bool 值然后 x TRUE FALSE ==> x .

现在我们减少

\x y . (IF x) ( (IF y) TRUE FALSE ) FALSE
\x y .     x  (     y  TRUE FALSE ) FALSE  -- using IF x         ==> x
\x y .     x  (     y             ) FALSE  -- using y TRUE FALSE ==> y
\x y . x y FALSE                           -- clean up

这个表达式仍然适用于真值表

AND TRUE  TRUE  = TRUE  TRUE  FALSE = TRUE
AND FALSE TRUE  = FALSE TRUE  FALSE = FALSE
AND TRUE  FALSE = TRUE  FALSE FALSE = FALSE
AND FALSE FALSE = FALSE FALSE FALSE = FALSE