我开始理解forall
关键字是如何在所谓的"存在类型"中使用的,如下所示:
data ShowBox = forall s. Show s => SB s
然而,这只是forall
使用方式的一个子集,我无法完全理解它在以下情况中的用法:
runST :: forall a. (forall s. ST s a) -> a
或者解释为什么它们是不同的:
foo :: (forall a. a -> a) -> (Char, Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))
或者整个RankNTypes
的东西...
我更喜欢清晰、没有术语的英语,而不是学术环境中常见的语言,我试图阅读的大多数解释(我可以通过搜索引擎找到的解释)都存在以下问题:
1.它们是不完整的,它们解释了这个关键字的一部分用法(比如"existential types"),这让我很高兴,直到我读到以完全不同的方式使用它的代码(比如上面的runST
,foo
和bar
)。
1.它们密密麻麻地塞满了假设,说明我已经读过本周流行的离散数学、范畴论或抽象代数的最新分支(如果我再也不读"查阅论文 * 无论什么 * 了解实现细节"这句话,那就太快了)。
1.它们的写作方式常常把简单的概念变成扭曲的、支离破碎的语法和语义。
所以...
回到真正的问题上,有谁能用清晰、平实的英语完整地解释forall
关键字(或者,如果它存在于某个地方,指出我错过的如此清晰的解释),而不认为我是一个沉浸在行话中的数学家?
- 编辑后添加:*
下面有两个高质量的答案,但不幸的是我只能选择一个最好的。诺曼的答案很详细,也很有用。以一种展示forall
的一些理论基础的方式来解释事物,同时向我展示它的一些实际含义。(作用域类型变量),并用代码和GHCi会话说明了所有概念。如果有可能选择两者都是最好的,我会。不幸的是,我不能,在仔细查看了这两个答案后,我认为yairchu的版本比norman的版本稍有优势,因为它有说明性的代码和附带的解释。因为我确实需要两个答案来理解这一点,当我在类型签名中看到forall
时,它不会给我留下一种微弱的恐惧感。
8条答案
按热度按时间uyto3xhc1#
让我们从一个代码示例开始:
此代码不能在纯Haskell 98中编译(语法错误)。它需要扩展以支持
forall
关键字。基本上,
forall
关键字有3种不同的常见用法(至少看起来是这样 *),每种用法都有自己的Haskell扩展:一米二氮一x,一米三氮一x/一米四氮一x,一米五氮一x。上面的代码在启用这两个选项时都不会出现语法错误,而只会在启用
ScopedTypeVariables
时出现类型检查。作用域类型变量:
作用域类型变量可以帮助用户指定
where
子句中代码的类型。它使val :: b
中的b
与foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b
中的b
相同。forall
,它实际上仍然隐式地存在。(来自Norman的回答:“通常这些语言省略了多态类型中的forall”)。这个声明是正确的,但是它指的是forall
的其他用途,而不是ScopedTypeVariables
的用途。N级类型:
首先,
mayb :: b -> (a -> b) -> Maybe a -> b
等效于mayb :: forall a b. b -> (a -> b) -> Maybe a -> b
,**ScopedTypeVariables
使能时除外。这意味着它适用于每个
a
和b
。假设你想做这样的事情。
这个
liftTup
的类型是什么?它是liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)
。为了了解原因,让我们尝试编写它:“嗯...为什么GHC推断元组必须包含两个相同类型的元组?让我们告诉它它们不必如此”
嗯,这里GHC不允许我们在
v
上应用liftFunc
,因为v :: b
和liftFunc
想要一个x
。我们真的希望我们的函数得到一个接受任何可能的x
的函数!所以不是
liftTup
对所有x
都有效,而是它得到的函数有效。存在量化:
让我们举个例子:
这与秩N型有何不同?
对于Rank-N-Types,
forall a
意味着表达式必须适合所有可能的a
。例如:空列表可以作为任何类型的列表使用。
因此,对于存在-量化,
data
定义中的forall
s意味着,所包含的值可以是任何合适的类型,而不是它必须是所有合适的类型。beq87vna2#
有谁能用清晰易懂的英语 * 完全 * 解释forall关键字吗?
以下是简单明了地解释
forall
的障碍:forall
没有简单的解释。forall
令人困惑。有Haskell或ML的经验是不够的,因为通常这些语言会从多态类型中省略forall
。(在我看来,这是语言设计的错误。)forall
的使用方式让我感到困惑。(我不是类型理论家,但我的工作让我接触到了很多类型理论,我对它很满意。)对我来说,混淆的主要原因是forall
被用来编码一个类型,而我自己更愿意用exists
来编写这个类型。这是由一个涉及量词和箭头的棘手的类型同构来证明的,每次我想理解它时,我都必须自己查找并计算出同构。如果您对类型同构的概念感到不舒服,或者如果您没有任何思考类型同构的实践,那么
forall
的使用将会阻碍您。forall
的一般概念总是相同的(绑定引入一个类型变量),不同用法的细节可能会有很大的不同。非正式英语不是解释这些变化的好工具。要真正理解发生了什么,你需要一些数学知识。在这种情况下,相关的数学知识可以在Benjamin Pierce的介绍性文本 * Types and Programming Languages * 中找到,这是一本非常好的书。至于你的特殊例子
runST
* 应该 * 会让你头疼。更高级别的类型(对于箭头左边的所有类型)在野外很难找到。我鼓励你阅读介绍runST
的文章:"Lazy Functional State Threads"。这是一篇非常好的论文,它会给你一个更好的直觉,特别是对于runST
类型,以及一般的更高级别的类型。解释花了几页,做得非常好,我不打算在这里压缩它。如果我调用
bar
,我可以简单地选择我喜欢的任何类型a
,然后我可以传递一个函数,从类型a
到类型a
。我可以传递函数(+1)
或函数reverse
。您可以将forall
视为表示"我现在可以选择类型"。(挑选类型的专业术语是"示例化"。)调用
foo
的限制要严格得多:foo
的参数必须是多态函数。对于这种类型,我只能传递给foo
的函数是id
或总是发散或出错的函数,如undefined
。原因是对于foo
,forall
在箭头的左边,因此作为foo
的调用者,我不必选择a
是什么,而是由foo
的 * 实现 * 来选择a
是什么。因为forall
位于箭头的左侧,而不是像bar
那样位于箭头的上方,示例化发生在函数的主体中而不是在调用点。forall
关键字的 * 完整 * 解释需要数学知识,只有学过数学的人才能理解。没有数学知识,即使是部分解释也很难理解。但也许我的部分非数学解释会有所帮助。去阅读Launchbury和Peyton Jones关于runST
的文章吧!forall
接受类型变量的名称,然后在forall的"below"有一个完整的类型。一个箭头接受两种类型(参数和结果类型)并形成一个新的类型(函数类型)。参数类型在箭头的"to left";它是抽象语法树中箭头的左子。示例:
forall a . [a] -> [a]
中,forall位于箭头上方;箭头左边的是[a]
。括号中的类型将被称为"箭头左侧的forall"(我在我正在开发的优化器中使用了类似的类型)。
dfty9e193#
我最初的回答是:
有谁能用清晰明了的英语完整地解释一下forall关键字吗
正如Norman所指出的,很难对类型论中的一个技术术语给予一个清晰、简单的英语解释,尽管我们都在努力。
关于“for all”,只有一件事需要记住:它将类型绑定到某个作用域。一旦你理解了这一点,一切都相当容易。它在类型级别上等价于'lambda'(或'let'的一种形式)-- Norman Ramsey在他的精彩回答中使用了“left”/“above”的概念来表达这个相同的作用域概念。
“forall”的大多数用法非常简单,您可以在GHC用户手册S7.8中找到介绍,尤其是关于嵌套形式“forall”的优秀S7.8.5。
在Haskell中,当类型被普遍量化时,我们通常不使用类型绑定器,如下所示:
相当于:
就是这样。
既然你现在可以将类型变量绑定到某个作用域,你就可以拥有除顶层(“通用量化”)之外的作用域,就像你的第一个例子,其中类型变量只在数据结构中可见,这就允许隐藏类型(“存在类型”),或者我们可以拥有任意的绑定嵌套(“秩N类型”)。
为了深入理解类型系统,你需要学习一些术语。这是计算机科学的本质。然而,像上面这样简单的用法,应该能够通过在值级别上与“let”进行类比而直观地掌握。Launchbury and Peyton Jones是一个很好的介绍。
huus2vyu4#
这里有一个简单明了的快速而肮脏的解释,你可能已经很熟悉了。
在Haskell中,
forall
关键字实际上只有一种用法,当你看到它时,它总是意味着同样的事情。普遍量化
forall a. f a
形式的类型。该类型的值可以被认为是函数,该函数以类型a
作为其参数,并返回类型f a
的值。除了在Haskell中这些类型参数由类型系统隐式传递。此“函数”必须给予你相同的值,不管它接收到什么类型,所以这个值是 * 多态 * 的。例如,考虑类型
forall a. [a]
,该类型的值接受另一个类型a
,并返回相同类型a
的元素列表,只有一种可能的实现,当然,它必须给予你一个空列表,因为a
可以是任何类型,空列表是元素类型中唯一多态的列表值(因为它没有元素)。或者
forall a. a -> a
类型,这样一个函数的调用者提供a
类型和a
类型的值,然后实现必须返回相同类型a
的值,这里也只有一个可能的实现,它必须返回给定的相同值。存在量化
一个 * 存在量化类型 * 将具有
exists a. f a
的形式,如果Haskell支持这种表示法的话。这种类型的值可以被认为是一个由a
类型和f a
类型的值组成的对(或“乘积”)。例如,如果你有一个
exists a. [a]
类型的值,你有一个某种类型的元素列表,它可以是任何类型,但是即使你不知道它是什么,你也可以对这样的列表做很多事情,你可以反转它,或者你可以计算元素的数量,或者执行任何其他不依赖于元素类型的列表操作。好的,等一下,为什么Haskell使用
forall
来表示一个“存在”类型,如下所示?这可能会让人感到困惑,但它实际上描述了数据构造函数 *
SB
的 * 类型:一旦构造了
ShowBox
类型的值,你可以认为它由两个部分组成:s
类型和s
类型的值,换句话说,它是一个存在量化类型的值。ShowBox
可以写成exists s. Show s => s
,如果Haskell支持这种表示法的话。和朋友们
既然如此,这些有什么不同?
我们先来看看
bar
,它有一个a
类型和一个a -> a
类型的函数并且产生一个(Char, Bool)
类型的值,我们可以选择Int
作为a
,并且给予它一个Int -> Int
类型的函数,但是foo
是不同的。它要求foo
的实现能够传递任何类型给我们给予它的函数,所以我们唯一可以合理地给它的函数是id
。现在我们应该能够理解
runST
类型的含义了:所以
runST
必须能够产生一个类型为a
的值,不管我们给予a
什么类型的值,为了达到这个目的,它使用了一个类型为forall s. ST s a
的参数,这个参数肯定会产生a
,而且,它必须能够产生类型为a
的值,而不管runST
的实现决定给予什么类型作为s
。因此,实际上
runST
函数是在告诉您:“你可以选择a
类型,只要我可以选择s
类型。”好吧,那又怎样呢?好处是这给
runST
的调用者设置了一个约束,因为类型a
根本不能包含类型s
,因为你不知道s
是什么类型,你不能给它传递一个类型ST s [s]
的值,实际上,这意味着runST
的实现可以知道任何涉及s
类型的值对于它自己的实现来说都是局部的,因此它可以自由地做否则不允许它做的事情,比如在适当的地方改变它们。类型保证了改变是局部的runST
的实现。runST
的类型是 * 秩-2多态类型 * 的示例,因为其参数的类型包含forall
限定符。上面foo
的类型也是秩-2。普通多态类型(如bar
)是秩-1,但如果参数的类型要求是多态的,则它变为秩-2。有自己的forall
量词。如果一个函数使用秩为2的参数,那么它的类型是秩为3的,以此类推。一般来说,一个使用秩为n
的多态参数的类型的秩为n + 1
。anauzrmj5#
它们密密麻麻地塞满了假设,说明我已经读过本周流行的离散数学、范畴论或抽象代数的最新分支(如果我再也不读“查阅论文了解实现细节”这句话,那就太快了)。
呃,那么简单的一阶逻辑呢?
forall
很明显是指universal quantification,在这种情况下,术语existential也更有意义。尽管如果存在exists
关键字则不会那么尴尬。量词是普遍的还是存在的,取决于量词相对于变量在词的哪一侧使用的位置。一个功能箭头,这有点混乱。所以,如果这没有帮助,或者你只是不喜欢符号逻辑,从更函数化编程的Angular 来看,你可以把类型变量看作是函数的(隐式的)type 参数,在这种意义上,带类型参数的函数不管出于什么原因,传统上都是用大写的lambda来写的,我在这里写为
/\
。因此,考虑
id
函数:我们可以将其重写为lambdas,将“type parameter”从类型签名中移除,并添加内联类型注解:
下面是对
const
执行的相同操作:因此,您的
bar
函数可能如下所示:注意,作为参数提供给
bar
的函数类型取决于bar
的type参数,请考虑是否使用类似以下的函数:这里
bar2
将函数应用于Char
类型的对象,因此为bar2
提供Char
以外的任何类型参数都会导致类型错误。另一方面,
foo
可能如下所示:与
bar
不同,foo
实际上根本不接受任何类型参数!它接受一个本身接受类型参数的函数,然后将该函数应用于两个不同的类型。因此,当您在类型签名中看到
forall
时,只需将其视为类型签名的lambda表达式。就像常规lambda一样,forall
的作用域尽可能向右扩展,直到包含括号,并且就像在常规lambda中绑定的变量一样,由forall
绑定的类型变量仅在量化表达式的作用域中。把类型变量和标签放在一起并返回一个新类型的函数是一个 type constructor,你可以这样写:
但是我们需要全新的符号,因为像
Either a b
这样的类型的编写方式已经暗示了“将函数Either
应用于这些参数”。另一方面,一个函数在其类型参数上进行某种“模式匹配”,为不同的类型返回不同的值,这是一个类型类 * 的 * 方法。稍微扩展一下我上面的
/\
语法,可以得出如下结论:我个人更喜欢 haskell 的语法...
“模式匹配”其类型参数并返回任意现有类型的函数是 * 类型族 * 或 * 函数依赖项 *--在前一种情况下,它甚至看起来已经非常像函数定义。
ltskdhd16#
有谁能用清晰明了的英语完整地解释forall关键字(或者,如果它存在于某个地方,指出我错过的一个如此清晰的解释),而不假设我是一个沉浸在行话中的数学家?
我将尝试解释
forall
在Haskell及其类型系统上下文中的含义和应用。但是在你理解之前,我想让你看一个Runar Bjarnason的演讲,题目是“Constraints Liberate, Liberties Constrain“。演讲中充满了来自真实的世界用例的例子以及Scala中的例子来支持这一说法,尽管它没有提到
forall
。我将在下面尝试解释forall
的观点。理解并相信这句话是非常重要的,所以我敦促你观看演讲(至少是部分)。
下面是一个非常常见的例子,展示了Haskell类型系统的表达能力:
foo :: a -> a
据说,给定这种类型签名,只有一个函数可以满足这种类型,那就是
identity
函数或更广为人知的id
。在我学习Haskell的开始阶段,我一直想知道以下功能:
它们都满足上面的类型签名,那么为什么Haskell的人声称只有
id
满足类型签名呢?这是因为在类型签名中隐藏了一个隐式的
forall
,实际的类型是:所以,现在让我们回到声明:束缚释放,自由束缚
将其转换为类型系统,此语句变为:
类型级别的约束变成术语级别的自由
以及
类型级别的自由变成术语级别的约束
现在,让我们看看
foo
函数的第一条语句:所以在类型签名上加一个约束
通过使用任何其他类型类等约束
a
也可以观察到同样的情况那么现在这个类型的签名是什么:
foo :: (Num a) => a -> a
转换为:这被称为存在量化,它翻译为 there exists
a
的一些示例,当函数输入a
类型的东西时,返回相同类型的东西,这些示例都属于Numbers集合。因此,我们可以看到添加了一个约束(
a
应该属于Numbers集合),释放了术语级别,使其具有多个可能的实现。现在来看看第二个语句,也就是实际解释
forall
的语句:现在让我们在类型级别释放函数:
现在,这转化为:
这意味着该类型签名的实现应当使得它对于所有环境都是
a -> a
。所以现在这开始限制我们在术语层面上。我们不能再写
因为如果我们将
a
作为Bool
放置,此实现将无法满足。a
可以是Char
、[Char]
或自定义数据类型。在所有情况下,它都应返回类似类型的内容。这种类型级别的自由性称为“通用量化”,唯一能够满足此要求的函数是通常称为
identity
函数因此,
forall
是类型级别的liberty
,其实际用途是将术语级别的constrain
应用于特定实现。a11xaf1n7#
这个关键字有不同用法的原因是,它实际上至少在两种不同类型的系统扩展中使用:高级类型和存在式。
也许最好是分别阅读和理解这两件事,而不是试图解释为什么'forall'在这两件事中同时是一个合适的语法位。
svgewumm8#
存在主义是怎样的存在主义?
对于存在-量化,
data
定义中的forall
s意味着,包含的值可以是任何合适的类型,而不是它必须是所有合适的类型。--yachiru's answer关于为什么
data
定义中的forall
同构于(exists a. a)
(伪Haskell)的解释可以在维基百科的“Haskell/Existentially quantified types”中找到。以下是简要的逐字摘要:
当模式匹配/解构
MkT x
时,x
的类型是什么?x
可以是任何类型(如forall
中所述),因此其类型为:因此,以下是同构的:
为了所有人就是为了所有人
我对这一切的简单解释是,“
forall
实际上意味着'for all'”。要做的一个重要区别是forall
对定义和函数应用程序的影响。forall
表示值或函数的定义必须是多态的。如果要定义的东西是多态的value,那么这意味着该值必须对所有合适的
a
有效,这是非常严格的。如果被定义的是一个多态的函数,那么它意味着这个函数必须对所有合适的
a
都有效,这并不是很严格,因为仅仅因为这个函数是多态的并不意味着被应用的参数必须是多态的。则相反地,任何合适的a
都可以应用到该函数。但是,参数的类型在函数定义中只能选择一次。如果一个
forall
在函数参数的类型内部(即一个Rank2Type
),则意味着applied参数必须是真正多态的,与forall
的思想一致,意味着definition是多态的。在这种情况下,参数的类型可以在函数定义("and is chosen by the implementation of the function", as pointed out by Norman)中选择多次。因此,存在
data
定义允许any**a
的原因是因为数据构造函数是一个多态函数:市场类型::
a -> *
这意味着任何
a
都可以应用于该函数,与多态值相反:值类型T::
a
这意味着valueT的定义必须是多态的,在这种情况下,
valueT
可以定义为所有类型的空列表[]
。差异数量
尽管
forall
的含义在ExistentialQuantification
和RankNType
中是一致的,但存在性还是有区别的,因为data
构造函数可以用于模式匹配。当模式匹配时,每个模式匹配为每个存在类型变量引入一个新的、不同的类型。这些类型不能与任何其他类型统一,也不能脱离模式匹配的范围。