Haskell 中教会编码布尔值的异或

Question

我目前正在尝试为 xor 实现一个 lambda 表达式。但是，我觉得我遗漏了一些东西，因为我从 bxor 表达式中得到了错误。我做错了什么？

true  = \t f -> t    -- always pick the first argument
false = \t f -> f    -- always pick the second argument

toBool = \b -> b True False

bnot = \b -> b true false

bxor = \b x -> b (bnot x) x

Answer 1

在类型环境中，需要小心。您的 lambda 项在非类型化设置中工作正常，但在类型化设置中需要一些调整。

我们需要为 Church 布尔值定义一个类型。让我们选择以下参数单态类型。

type B a = a -> a -> a

然后，让我们添加类型注释来检查问题所在：

true :: B a
true  = \t f -> t

false :: B a
false = \t f -> f

toBool :: B Bool -> Bool
toBool = \b -> b True False

到目前为止，还不错。然而：

bnot :: B a -> B a
bnot = \b -> b false true

产生类型错误，因为例如false 的类型为 B a，而非 a，因此应用程序 b false 的类型不正确。我们可以通过添加几个 a 个参数 x y 并相应地简化函数来解决这个问题。

bnot = \b x y -> b (false x y) (true x y)
-- or, more simply:
bnot = \b x y -> b y x
-- or even
bnot = flip

这种类型的检查。同样，我们可以修改 bxor 使其类型检查：

bxor :: B a -> B a -> B a       
bxor = \b1 b2 x y -> b1 (bnot b2 x y) (b2 x y)

或者，使用 impredicative 布尔值的 Church 编码，我们可以使您的原始代码按原样进行类型检查，除了添加相关的类型签名。这需要更高级别的类型。

{-# LANGUAGE Rank2Types #-}

type BI = forall a. a -> a -> a

trueI :: BI
trueI = true

falseI :: BI
falseI = false

toBoolI :: BI -> Bool
toBoolI = \b -> b True False

bnotI :: BI -> BI
bnotI = \b -> b falseI trueI

bxorI :: BI -> BI -> BI
bxorI = \b x -> b (bnotI x) x

Haskell 中教会编码布尔值的异或

xor of Church-encoded booleans in Haskell

lambda

haskell

xor