Haskell 中的两个函数看似相等但不同
Two functions seem equal but different in Haskell
我正在尝试在 Haskell 中实现没有 Prelude 的布尔值。
表达式，beq true true "TRUE" "FALSE"求值时，没问题。但是当我尝试评估 beq' true true "TRUE" "FALSE" 时，它因预期类型和实际类型之间的一些差异而失败。
这是代码。
import qualified Prelude as P
i = \x -> x
k = \x y -> x
ki = k i
true = k
false = ki
not = \p -> p false true
beq = \p q -> p (q true false) (q false true)
beq' = \p q -> p q (not q)
所以我检查了论文的推断类型。
*Main> :type beq
beq
:: (t1 -> t1 -> t2)
-> ((p1 -> p1 -> p1) -> (p2 -> p2 -> p2) -> t1) -> t2
*Main> :type beq'
beq'
:: (((p1 -> p2 -> p2) -> (p3 -> p4 -> p3) -> t1) -> t1 -> t2)
-> ((p1 -> p2 -> p2) -> (p3 -> p4 -> p3) -> t1) -> t2
而且不相等。
这是问题。
我认为它具有相同的类型签名，因为 beq 和 beq' 在折叠和替换时似乎产生相同的结果。就像有很多方法可以实现一个功能。但事实并非如此。 Haskell?
如果我想用函数not写beq，我怎样才能让它工作？
如何修复编码
Church 编码在无类型演算中工作得很好。
添加类型后，事情变得更加复杂。例如，对于简单类型，编码会丢失。如果支持更高的等级，则可以通过多态性恢复它们。请注意，类型推断不能很好地处理更高类型，因此需要一些显式类型注释。
比如你的not应该写成：
{-# LANGUAGE RankNTypes #-}
type ChBool = forall a. a -> a -> a
not :: ChBool -> ChBool
not f x y = f y x
将布尔值建模为多态函数很重要，否则它们只能用于单一类型，导致许多示例失败。例如，考虑
foo :: Bool -> (Int, String)
foo b = (b 3 2, b "aa" "bb")
这里b需要使用两次，一次在Ints，一次在Strings。如果 Bool 不是多态的，这将失败。
为什么 beta-reduction 更改推断类型
更进一步，你似乎确信可以beta-reduce Haskell 表达式和归约前后的推断类型必须相同。总的来说，正如您在实验中发现的那样，情况并非如此。要了解原因，这里有一个简单的例子：
id1 x = x
这里的推断类型显然是id1 :: forall a. a -> a。请考虑以下变体：
id2 x = (\ _ -> x) e
请注意 id2 beta-reduce 到 id1、 任何 e 可能 。但是，通过仔细选择 e，我们可以限制 x 的类型。例如。让我们选择 e = x "hello"
id2 x = (\ _ -> x) (x "hello")
现在，推断类型为 id2 :: forall b. (String -> b) -> String -> b，因为 x 只能是 String 接受函数。 e 不会被评估并不重要，类型推断算法无论如何都会做出 well-typed 。这使得 id2 的推断类型不同于 id1.
我正在尝试在 Haskell 中实现没有 Prelude 的布尔值。
表达式，beq true true "TRUE" "FALSE"求值时，没问题。但是当我尝试评估 beq' true true "TRUE" "FALSE" 时，它因预期类型和实际类型之间的一些差异而失败。
这是代码。
import qualified Prelude as P
i = \x -> x
k = \x y -> x
ki = k i
true = k
false = ki
not = \p -> p false true
beq = \p q -> p (q true false) (q false true)
beq' = \p q -> p q (not q)
所以我检查了论文的推断类型。
*Main> :type beq
beq
:: (t1 -> t1 -> t2)
-> ((p1 -> p1 -> p1) -> (p2 -> p2 -> p2) -> t1) -> t2
*Main> :type beq'
beq'
:: (((p1 -> p2 -> p2) -> (p3 -> p4 -> p3) -> t1) -> t1 -> t2)
-> ((p1 -> p2 -> p2) -> (p3 -> p4 -> p3) -> t1) -> t2
而且不相等。
这是问题。
我认为它具有相同的类型签名，因为
beq和beq'在折叠和替换时似乎产生相同的结果。就像有很多方法可以实现一个功能。但事实并非如此。 Haskell? 中是否有一些秘密规则和语法
如果我想用函数
not写beq，我怎样才能让它工作？
如何修复编码
Church 编码在无类型演算中工作得很好。
添加类型后，事情变得更加复杂。例如，对于简单类型，编码会丢失。如果支持更高的等级，则可以通过多态性恢复它们。请注意，类型推断不能很好地处理更高类型，因此需要一些显式类型注释。
比如你的not应该写成：
{-# LANGUAGE RankNTypes #-}
type ChBool = forall a. a -> a -> a
not :: ChBool -> ChBool
not f x y = f y x
将布尔值建模为多态函数很重要，否则它们只能用于单一类型，导致许多示例失败。例如，考虑
foo :: Bool -> (Int, String)
foo b = (b 3 2, b "aa" "bb")
这里b需要使用两次，一次在Ints，一次在Strings。如果 Bool 不是多态的，这将失败。
为什么 beta-reduction 更改推断类型
更进一步，你似乎确信可以beta-reduce Haskell 表达式和归约前后的推断类型必须相同。总的来说，正如您在实验中发现的那样，情况并非如此。要了解原因，这里有一个简单的例子：
id1 x = x
这里的推断类型显然是id1 :: forall a. a -> a。请考虑以下变体：
id2 x = (\ _ -> x) e
请注意 id2 beta-reduce 到 id1、 任何 e 可能 。但是，通过仔细选择 e，我们可以限制 x 的类型。例如。让我们选择 e = x "hello"
id2 x = (\ _ -> x) (x "hello")
现在，推断类型为 id2 :: forall b. (String -> b) -> String -> b，因为 x 只能是 String 接受函数。 e 不会被评估并不重要，类型推断算法无论如何都会做出 well-typed 。这使得 id2 的推断类型不同于 id1.