Haskell类型变量是隐式量化的。关键字forall
出现在::
之后。
例如,const
类型签名
const :: a -> b -> a
写为:
const :: forall a b. a -> b -> a
我的问题是:我如何有效地推断签名
const :: forall a. a -> a -> a
我试着使用我从一阶逻辑学中学到的概念,比如“普适消去法”,但从理论的Angular 来看,我无法证明这一点。
当然,这是有意义的,因为没有什么排除b
与a
相同。
为什么我不能使用推理规则呢?因为我不能在第二个量词上使用消去法,因为变量会冲突。我不能用a
示例化b
。
2条答案
按热度按时间toe950271#
请考虑:
你不能从(1)推断出(2);如果可以的话,这就意味着
const
* 总是 * 有一个适合forall a. a -> a -> a
的类型(在(1)中并不明显,因为我们还没有应用足够的推理步骤),但是我显然可以在const True 'a'
这样的情况下使用const
,其中const
有Bool -> Char -> Bool
类型。你能做的就是意识到(2)是的 * 示例化 *(1).
b
与a
一般不相同,但是,(正如你所说的)没有什么能阻止b
在任何一个特定的用法中与a
是同一个东西。因此,从使用const
的上下文中,你可能能够推断那个特定的用法的类型为forall a. a -> a -> a
。例如,这发生在:您还可以从
const :: forall a b. a -> b -> a
中得知,如果您选择将b
示例化为与a
相同,则会得到const :: forall a -> a -> a
。其中我们总是为b
选择与为a
所做的相同的事情。为此,我们只需将
b
替换为a
即可(在我们正在示例化的量词的作用域中,但这里是整个表达式)。您表示怀疑您是否可以这样做,因为变量会冲突,但是示例化一个变量使其与另一个变量相同是我们在这里所做的重点。意外地 * 改变了表达式,给变量取了相同的名字,而这些名字本应该是不同的;在这里,我们是经过深思熟虑的选择来检验它们"不“不同的特殊情况。但是,没有从
const :: forall a -> b -> a
(没有任何使用它的上下文)到const :: forall a. a -> a -> a
的纯推理链,因为当你做出这种改变时,你正在削弱/专门化const
;如果不添加额外的信息来限制b
与a
相同(用Haskelly的话来说,这是一个额外的a ~ b
约束),推理规则就不会把你从(1)带到(2)。wfauudbj2#
以下内容以评论开头,已移至此处。
因为我不能在第二个量词上使用消去法,因为变量会冲突。
我认为你错了。事实上你可以使用消元法,而变量的冲突与普适消元法无关。[从我从下面的资料中了解到的情况来看,有时冲突是相关的,有时则不是。]
你能告诉我哪种自然演绎系统允许在普适消去推理中使用约束变量吗?
Chapter 8 of Stanford Introduction to Logic将 * 通用消除(UE)* 定义为
和
我们说,项τ对于句子φ中的变量ν是自由的,当且仅当ν在τ中某个变量的量词的范围内没有自由出现。
有了这一点和 * 通用介绍(UI)*,我认为
这就剩下了声称
a is free for a in ∀b.a⇒(b⇒a)
等。在
∀b.a⇒(b⇒a)
中不存在a
的量词,因此a
不会在∀b.a⇒(b⇒a)
中a
的(不存在的)量词的范围内自由出现。