357

我开始了解如何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. 它们是不完整的。他们解释了这个关键字使用的一部分(比如“存在类型”),这让我感到很高兴,直到我阅读了以完全不同的方式使用它的代码(比如runST,foobar以上)。
  2. 它们充满了假设,这些假设是我在本周流行的离散数学、范畴论或抽象代数的任何分支中读到的最新消息。(如果我再也没有读到“请参阅论文以了解实施细节”的话那就太早了。)
  3. 它们的编写方式经常将甚至简单的概念变成曲折扭曲和支离破碎的语法和语义。

所以...

关于实际问题。任何人都可以用清晰、简单的英语完整地解释这个forall关键字(或者,如果它存在于某个地方,指出我错过的如此清晰的解释)而不认为我是一个沉浸在行话中的数学家吗?


编辑添加:

下面的高质量答案中有两个突出的答案,但不幸的是,我只能选择一个作为最佳答案。 诺曼的回答详细而有用,以一种显示一些理论基础的方式解释事物,forall同时向我展示了它的一些实际含义。 亚初的回答涵盖了其他人没有提到的领域(作用域类型变量),并用代码和 GHCi 会话说明了所有概念。如果可以选择最好的,我会的。不幸的是,我不能,并且在仔细查看了这两个答案之后,我认为由于说明性代码和附加的解释,yairchu 稍微优于 Norman 的。然而,这有点不公平,因为我确实需要两个答案来理解这一点,以至于forall当我在类型签名中看到它时不会让我有一种微弱的恐惧感。

4

8 回答 8

301

让我们从一个代码示例开始:

foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b
foob postProcess onNothin onJust mval =
    postProcess val
    where
        val :: b
        val = maybe onNothin onJust mval

此代码在普通 Haskell 98 中无法编译(语法错误)。它需要扩展来支持forall关键字。

基本上,关键字有 3种不同的常见用法forall(或者至少看起来是这样),并且每个都有自己的 Haskell 扩展:ScopedTypeVariablesRankNTypes/ Rank2TypesExistentialQuantification

上面的代码在启用其中任何一个时都不会出现语法错误,而只会在启用时进行类型检查ScopedTypeVariables

作用域类型变量:

作用域类型变量有助于指定where子句内代码的类型。它使bin与inval :: b相同。bfoob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b

一个令人困惑的点:你可能听说当你forall从一个类型中省略时,它实际上仍然隐式存在。(来自诺曼的回答:“通常这些语言从多态类型中省略了 forall”)。这种说法是正确的,它指的是 的其他用途forall,而不是ScopedTypeVariables用途。

Rank-N-类型:

让我们从mayb :: b -> (a -> b) -> Maybe a -> b等效于开始mayb :: forall a b. b -> (a -> b) -> Maybe a -> b除了何时启用ScopedTypeVariables

这意味着它适用于所有ab

假设你想做这样的事情。

ghci> let putInList x = [x]
ghci> liftTup putInList (5, "Blah")
([5], ["Blah"])

这必须是什么类型liftTup?是liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)。要了解原因,让我们尝试编写代码:

ghci> let liftTup liftFunc (a, b) = (liftFunc a, liftFunc b)
ghci> liftTup (\x -> [x]) (5, "Hello")
    No instance for (Num [Char])
    ...
ghci> -- huh?
ghci> :t liftTup
liftTup :: (t -> t1) -> (t, t) -> (t1, t1)

“嗯..为什么 GHC 推断元组必须包含两个相同类型的?让我们告诉它它们不必是”

-- test.hs
liftTup :: (x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

ghci> :l test.hs
    Couldnt match expected type 'x' against inferred type 'b'
    ...

唔。所以这里 GHC 不允许我们申请liftFuncv因为v :: b并且liftFunc想要一个x. 我们真的希望我们的函数能够接受任何可能的函数x

{-# LANGUAGE RankNTypes #-}
liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

所以这并不是liftTup对所有人都x有效,而是它得到的功能。

存在量化:

让我们举个例子:

-- test.hs
{-# LANGUAGE ExistentialQuantification #-}
data EQList = forall a. EQList [a]
eqListLen :: EQList -> Int
eqListLen (EQList x) = length x

ghci> :l test.hs
ghci> eqListLen $ EQList ["Hello", "World"]
2

这与 Rank-N-Types 有什么不同?

ghci> :set -XRankNTypes
ghci> length (["Hello", "World"] :: forall a. [a])
    Couldnt match expected type 'a' against inferred type '[Char]'
    ...

使用 Rank-N-Types,forall a意味着您的表达式必须适合所有可能a的 s。例如:

ghci> length ([] :: forall a. [a])
0

空列表确实可以作为任何类型的列表。

所以对于存在量化,定义中forall的 sdata意味着包含的值可以任何合适的类型,而不是它必须所有合适的类型。

于 2010-06-18T17:44:06.940 回答
135

任何人都可以用清晰、简单的英语完整地解释 forall 关键字吗?

不。(好吧,也许唐·斯图尔特可以。)

以下是简单、清晰的解释或的障碍forall

  • 是一个量词。你必须至少有一点逻辑(谓词演算)才能看到一个普遍的或存在的量词。如果您从未见过谓词演算或对量词不满意(而且我在博士资格考试期间看到学生不习惯),那么对您来说,没有简单的解释forall

  • 它是一个类型量词。如果您还没有看过System F并且没有练习过编写多态类型,那么您会感到forall困惑。使用 Haskell 或 ML 的经验是不够的,因为这些语言通常会省略forallfrom 多态类型。(在我看来,这是一个语言设计错误。)

  • 特别是在 Haskell 中,forall它的使用方式让我感到困惑。(我不是类型理论家,但我的工作让我接触到了很多类型理论,我对它很满意。)对我来说,混淆的主要来源forall是用于编码一个类型我自己更喜欢用exists. 这是由涉及量词和箭头的一些棘手的类型同构证明的,每次我想理解它时,我都必须自己查找并计算出同构。

    如果您对类型同构的想法不满意,或者如果您没有任何思考类型同构的练习,那么这种使用forall会阻碍您。

  • 虽然 的一般概念forall始终相同(绑定以引入类型变量),但不同用途的细节可能会有很大差异。非正式英语不是解释变化的好工具。要真正了解发生了什么,您需要一些数学知识。在这种情况下,相关的数学可以在 Benjamin Pierce 的介绍性文本Types and Programming Languages中找到,这是一本非常好的书。

至于你的具体例子,

  • runST 应该让你头疼。在野外很少发现更高等级的类型(箭头左侧)。我鼓励您阅读介绍了runSTLazy Functional State Threads”的论文。这是一篇非常好的论文,它将为您提供更好的直觉,runST特别是对于特定类型和一般更高级别的类型。解释用了好几页,写的非常好,这里我就不尝试浓缩了。

  • 考虑

    foo :: (forall a. a -> a) -> (Char,Bool)
    bar :: forall a. ((a -> a) -> (Char, Bool))
    

    如果我调用bar,我可以简单地选择我喜欢的任何类型a,并且可以将一个函数从 type 传递a给 type a。例如,我可以传递 function(+1)或 function reverse。您可以将其forall视为“我现在可以选择类型”。(选择类型的技术术语是实例化。)

    调用的限制foo要严格得多:参数 tofoo 必须是多态函数。对于这种类型,我可以传递给的唯一函数fooid或者总是发散或错误的函数,例如undefined. 原因是 ,fooforall箭头左侧的,所以作为fooI 的调用者不能选择是什么a,而是由 that 的实现来选择。因为是在箭头的左侧,而不是在箭头上方,所以实例化发生在函数体中,而不是在调用站点。fooaforallbar

总结:关键字的完整解释forall需要数学,只有学过数学的人才能理解。没有数学,即使是部分解释也很难理解。但也许我的部分非数学解释会有所帮助。去阅读 Launchbury 和 Peyton JonesrunST吧!


附录:行话“上方”、“下方”、“左侧”。这些与编写类型的文本方式无关,与抽象语法树有关。在抽象语法中,aforall采用类型变量的名称,然后在 forall 的“下方”有一个完整类型。一个箭头有两种类型(参数类型和结果类型)并形成一个新类型(函数类型)。参数类型是箭头的“左侧”;它是抽象语法树中箭头的左孩子。

例子:

  • forall a . [a] -> [a]中,forall 位于箭头上方;箭头左边是什么[a]

  • forall n f e x . (forall e x . n e x -> f -> Fact x f) 
                  -> Block n e x -> f -> Fact x f
    

    括号中的类型将被称为“箭头左侧的 forall”。(我在我正在研究的优化器中使用这样的类型。)

于 2010-06-18T16:19:23.050 回答
57

我原来的答案:

任何人都可以用清晰、简单的英语完整地解释 forall 关键字吗

正如 Norman 所指出的,很难对类型理论中的技术术语给出清晰、通俗的英语解释。不过我们都在努力。

关于“forall”,只有一件事需要记住:它将类型绑定到某个范围。一旦你明白这一点,一切都相当容易。它在类型级别上等同于“lambda”(或“let”的一种形式)——Norman Ramsey 在他的出色回答中使用“左”/“上方”的概念来传达同样的范围概念。

'forall' 的大多数用法都非常简单,您可以在GHC 用户手册 S7.8中找到它们的介绍,尤其是在嵌套形式的 'forall' 上出色的 S7.8.5 。

在 Haskell 中,当类型被普遍量化时,我们通常会省略类型的绑定器,如下所示:

length :: forall a. [a] -> Int

相当于:

length :: [a] -> Int

就是这样。

由于您现在可以将类型变量绑定到某个范围,因此您可以拥有顶级以外的范围(“普遍量化”),就像您的第一个示例一样,其中类型变量仅在数据结构中可见。这允许隐藏类型(“存在类型”)。或者我们可以任意嵌套绑定(“rank N types”)。

要深入理解类型系统,您需要学习一些行话。这就是计算机科学的本质。然而,像上面这样的简单用途,应该可以通过与价值层面上的“让”类比来直观地掌握。Launchbury 和 Peyton Jones是一个很好的介绍。

于 2010-06-18T18:02:44.673 回答
35

这是您可能已经熟悉的通俗易懂的快速而肮脏的解释。

在 Haskell 中,forall关键字实际上只以一种方式使用。当你看到它时,它总是意味着同样的事情。

通用量化

全称量化类型是形式的一种forall a. f a。该类型的值可以被认为是一个函数,它接受一个类型 a作为其参数并返回一个类型的f a。除了在 Haskell 中,这些类型参数由类型系统隐式传递。这个“函数”无论接收到哪种类型,都必须给你相同的值,所以这个值是polymorphic

例如,考虑类型forall a. [a]。该类型的值采用另一种类型a,并返回一个相同类型的元素列表a。当然,只有一种可能的实现方式。它必须给你一个空列表,因为a绝对可以是任何类型。空列表是其元素类型中唯一多态的列表值(因为它没有元素)。

或类型forall a. a -> a。此类函数的调用者提供 type 的类型a和值a。然后实现必须返回相同类型的值a。再次只有一种可能的实现方式。它必须返回与给定相同的值。

存在量化

如果Haskell 支持该符号,则存在量化类型将具有形式。exists a. f a该类型的值可以被认为是由一个类型和一个类型的值组成的一对(或“产品”)。af a

例如,如果你有一个 type 的值exists a. [a],你就有一个某种类型的元素列表。它可以是任何类型,但即使你不知道它是什么,你也可以对这样的列表做很多事情。您可以反转它,或者您可以计算元素的数量,或者执行任何其他不依赖于元素类型的列表操作。

好的,请稍等。为什么 Haskell 使用forall如下所示的“存在”类型来表示?

data ShowBox = forall s. Show s => SB s

它可能会令人困惑,但它确实描述了数据构造函数的类型 SB

SB :: forall s. Show s => s -> ShowBox

一旦构造,您可以将类型的值ShowBox视为由两件事组成。它是一个类型s和一个类型的值s。换句话说,它是一个存在量化类型的值。如果 Haskell 支持这种表示法,那么ShowBox真的可以写成。exists s. Show s => s

runST和朋友

鉴于此,这些有何不同?

foo :: (forall a. a -> a) -> (Char,Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

我们先来看看bar。它接受一个类型a和一个类型的函数a -> a,并产生一个类型的值(Char, Bool)。例如,我们可以选择Int作为a并给它一个类型的函数Int -> Int。但foo不一样。它要求实现foo能够将它想要的任何类型传递给我们给它的函数。所以我们可以合理地赋予它的唯一功能是id.

我们现在应该能够处理类型的含义runST

runST :: forall a. (forall s. ST s a) -> a

所以runST必须能够产生一个类型的值a,不管我们给出什么类型a。为此,它使用一个类型的参数,该参数forall s. ST s a肯定必须以某种方式产生a. 更重要的是,它必须能够产生 type 的值,a无论实现runST决定给出什么类型 as s

所以实际上该runST功能是在对您说:“a只要我可以选择类型,您就可以选择类型s。”

好的,那又怎样?好处是这对调用者施加了限制,runST因为类型a根本不能涉及类型s,因为您不知道s将是什么类型。例如,您不能将 type 的值传递给它ST s [s]。这在实践中意味着 的实现runST可以知道任何涉及该类型的值s对于它自己的实现来说都是本地的,所以它可以自由地做一些原本不允许做的事情,比如在适当的地方改变它们。该类型保证突变是本地的实现runST

的类型是rank-2 多态类型runST的一个例子,因为它的参数类型包含一个量词。上面的类型也是 rank 2。一个普通的多态类型,如 的,是 rank-1,但如果参数的类型需要是多态的,并且有自己的量词,它就会变成 rank-2。如果一个函数接受 rank-2 参数,那么它的类型是 rank-3,依此类推。通常,采用 rank 多态参数的类型具有 rank 。forallfoobarforallnn + 1

于 2013-03-16T18:12:20.397 回答
32

它们充满了假设,即我已经阅读了本周流行的离散数学、范畴论或抽象代数的最新分支。(如果我再也没有读到“请参阅论文以了解实施细节”的话,那就太早了。)

呃,那简单的一阶逻辑呢?forall很清楚地提到了全称量化,在这种情况下,术语存在主义也更有意义,尽管如果有一个exists关键字就不会那么尴尬了。量化是否有效地普遍或存在取决于量词的位置相对于变量在函数箭头的哪一侧使用的位置,这有点令人困惑。

因此,如果这没有帮助,或者如果您只是不喜欢符号逻辑,那么从更函数式编程的角度来看,您可以将类型变量视为函数的(隐式)类型参数。在这种意义上,采用类型参数的函数传统上是使用大写的 lambda 编写的,无论出于何种原因,我将在这里写为/\.

因此,考虑id函数:

id :: forall a. a -> a
id x = x

我们可以将其重写为 lambda,将“类型参数”移出类型签名并添加内联类型注释:

id = /\a -> (\x -> x) :: a -> a

这是相同的事情const

const = /\a b -> (\x y -> x) :: a -> b -> a

所以你的bar功能可能是这样的:

bar = /\a -> (\f -> ('t', True)) :: (a -> a) -> (Char, Bool)

请注意,bar作为参数提供的函数的类型取决于bar的类型参数。考虑一下你是否有这样的东西:

bar2 = /\a -> (\f -> (f 't', True)) :: (a -> a) -> (Char, Bool)

这里bar2是将函数应用于 type 的东西Char,因此提供bar2任何类型参数以外的任何类型参数Char都会导致类型错误。

另一方面,这foo可能看起来像:

foo = (\f -> (f Char 't', f Bool True))

不像bar,foo实际上根本不接受任何类型参数!它接受一个本身接受类型参数的函数,然后将该函数应用于两种不同的类型。

因此,当您forall在类型签名中看到 a 时,只需将其视为类型签名的 lambda 表达式。就像常规 lambda 一样,范围forall尽可能向右延伸,直到括号,就像在常规 lambda 中绑定的变量一样,由 a 绑定的类型变量forall仅在量化表达式的范围内。


Post scriptum:也许您可能想知道——既然我们正在考虑使用类型参数的函数,为什么我们不能对这些参数做一些比将它们放入类型签名中更有趣的事情呢?答案是我们可以!

将类型变量与标签放在一起并返回新类型的函数是类型构造函数,您可以编写如下内容:

Either = /\a b -> ...

但是我们需要全新的符号,因为这种类型的编写方式,例如Either a b,已经暗示了“将函数Either应用于这些参数”。

另一方面,在其类型参数上进行某种“模式匹配”、为不同类型返回不同值的函数是类型类的方法。对我上面的语法稍作扩展/\,建议如下:

fmap = /\ f a b -> case f of
    Maybe -> (\g x -> case x of
        Just y -> Just b g y
        Nothing -> Nothing b) :: (a -> b) -> Maybe a -> Maybe b
    [] -> (\g x -> case x of
        (y:ys) -> g y : fmap [] a b g ys 
        []     -> [] b) :: (a -> b) -> [a] -> [b]

就个人而言,我认为我更喜欢 Haskell 的实际语法......

“模式匹配”其类型参数并返回任意现有类型的函数是类型族函数依赖项——在前一种情况下,它甚至看起来已经很像函数定义了。

于 2010-06-18T16:56:00.143 回答
12

任何人都可以用清晰、简单的英语完全解释 forall 关键字(或者,如果它存在于某个地方,请指出我错过的如此清晰的解释),而不认为我是一个沉浸在行话中的数学家?

我将尝试解释forallHaskell 及其类型系统上下文中的含义以及可能的应用。

但在您理解之前,我想引导您参加 Runar Bjarnason 的一个非常通俗易懂且精彩的演讲,题为“ Constraints Liberate, Liberties Constrain ”。该演讲充满了来自现实世界用例的示例以及 Scala 中的示例来支持这一说法,尽管它没有提到forall. 我将尝试解释forall下面的观点。

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

消化并相信此声明以进行以下解释非常重要,因此我敦促您观看演讲(至少部分内容)。

现在一个非常常见的例子,展示了 Haskell 类型系统的表现力是这个类型签名:

foo :: a -> a

据说给定这个类型签名,只有一个函数可以满足这个类型,那就是identity函数或者更通俗的说法id

在我学习 Haskell 的开始阶段,我一直想知道以下函数:

foo 5 = 6

foo True = False

它们都满足上述类型签名,那么为什么 Haskell 的人声称id只有它满足类型签名呢?

那是因为forall类型签名中隐藏了一个隐含的内容。实际类型是:

id :: forall a. a -> a

所以,现在让我们回到这句话:约束解放,自由约束

将其转换为类型系统,此语句变为:

类型级别的约束,成为术语级别的自由

类型级别的自由成为术语级别的约束


让我们尝试证明第一个陈述:

类型级别的约束..

所以对我们的类型签名施加约束

foo :: (Num a) => a -> a

成为术语级别 的自由给了我们编写所有这些的自由或灵活性

foo 5 = 6
foo 4 = 2
foo 7 = 9
...

a通过使用任何其他类型类等进行约束也可以观察到相同的情况

所以现在这个类型签名:foo :: (Num a) => a -> a转换为:

∃a , st a -> a, ∀a ∈ Num

这被称为存在量化,它转换为存在一些实例,a其中一个函数在输入某种类型a的东西时返回相同类型的东西,并且这些实例都属于数字集合。

因此我们可以看到添加一个约束(a应该属于数字集),释放术语级别以具有多种可能的实现。


现在来到第二个陈述和一个实际上带有解释的陈述forall

类型级别的自由成为术语级别的约束

所以现在让我们在类型级别解放函数:

foo :: forall a. a -> a

现在这转化为:

∀a , a -> a

这意味着这种类型签名的实现应该a -> a适用于所有情况。

所以现在这开始在术语级别限制我们。我们不能再写了

foo 5 = 7

因为如果我们把这个实现a作为Bool. a可以是 aChar或 a[Char]或自定义数据类型。在所有情况下,它都应该返回类似类型的东西。这种类型级别的自由就是所谓的通用量化,唯一可以满足这一点的功能是

foo a = a

这就是通常所说的identity函数


因此forallliberty在类型级别,其实际目的是对constrain特定实现的术语级别。

于 2017-10-19T00:35:28.180 回答
9

这个关键字有不同用法的原因是它实际上至少用于两种不同的类型系统扩展:更高级别的类型和存在主义。

最好单独阅读和理解这两件事,而不是试图解释为什么“forall”同时在两者中是适当的语法。

于 2010-06-18T17:26:12.980 回答
4

存在主义如何存在?

对于存在量化,定义中forall的 sdata意味着包含的值可以任何合适的类型,而不是必须所有合适的类型。——矢千的回答

可以在wikibooks 的 "Haskell/Existentially quantified types"forall中找到关于为什么data定义与(伪 Haskell)同构的解释。(exists a. a)

以下是一个简短的逐字摘要:

data T = forall a. MkT a -- an existential datatype
MkT :: forall a. a -> T -- the type of the existential constructor

当模式匹配/解构MkT x时,类型是x什么?

foo (MkT x) = ... -- -- what is the type of x?

x可以是任何类型(如 中所述forall),因此它的类型是:

x :: exists a. a -- (pseudo-Haskell)

因此,以下是同构的:

data T = forall a. MkT a -- an existential datatype
data T = MkT (exists a. a) -- (pseudo-Haskell)

forall 是 forall 的意思

我对这一切的简单解释是,“forall真正意味着‘为所有人’”。一个重要的区别是对forall定义功能应用的影响。

Aforall表示值或函数的定义必须是多态的。

如果被定义的东西是一个多态,那么这意味着该值必须对所有合适的都有效a,这是相当严格的。

如果被定义的东西是一个多态函数,那么这意味着该函数必须对所有合适的函数都有效a,这不是限制性的,因为仅仅因为函数是多态的并不意味着所应用的参数必须是多态的。也就是说,如果该函数对所有 有效a,则相反,任何合适的a都可以应用于该函数。但是,参数的类型只能在函数定义中选择一次。

如果 aforall在函数参数的类型(即 a Rank2Type)内,则意味着应用的参数必须是真正的多态,以符合forall意味着定义是多态的思想。在这种情况下,参数的类型可以在函数定义中多次选择(“并且由函数的实现选择”,正如 Norman 所指出的

因此,存在data定义允许any a的原因是数据构造函数是一个多态函数

MkT :: forall a. a -> T

一种MKT::a -> *

这意味着任何a可以应用于该功能。与多态相反:

valueT :: forall a. [a]

一种价值T ::a

这意味着 valueT 的定义必须是多态的。在这种情况下,valueT可以定义为[]所有类型的空列表。

[] :: [t]

差异

即使 for 的含义在 and 中是forall一致的,existentials 也有区别,因为构造函数可以用于模式匹配。如ghc 用户指南中所述:ExistentialQuantificationRankNTypedata

模式匹配时,每个模式匹配都会为每个存在类型变量引入一个新的、不同的类型。这些类型不能与任何其他类型统一,也不能脱离模式匹配的范围。

于 2015-02-06T18:49:31.840 回答