为什么对于forall a. a这种类型,它不被认为是Int的子类型,但我可以在需要Int类型的任何地方使用一个类型为forall a. a的表达式?

17
考虑以下一对函数定义,它们通过类型检查器:
a :: forall a. a
a = undefined

b :: Int
b = a

也就是说,类型为forall a. a的表达式可以被用在期望类型为Int的地方。这对我来说看起来很像子类型化,但据称Haskell的类型系统缺乏子类型化。这些替换形式有何不同?

这个问题不仅限于forall a. a。其他例子包括:

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

idInt :: Int -> Int
idInt = id

undefined 不是 子类型化。这是一个错误。你为什么认为它是子类型化? - AJF
4
这是一个不同的例子:mempty :: forall m. Monoid m => mlet x = mempty :: [Int]。意思是,mempty 是一个泛型函数,它接受一个符合 Monoid 接口的类型 m 并返回一个该类型的空值。在这个例子中,x 被定义为 [Int] 类型的空值。 - rampion
5
非终止(bottom)是关于值的。而这个问题则是关于类型的。 - user1804599
1
只是一个实际的例子:你可以写 [Int],但你不能写 [forall a. a](除非你启用了不太适用于类型推断的不确定性)。 - chi
4
我想提一下 lens 库使用了全称多态和类型类编码出相当令人印象深刻的 "子类型层次结构",所以无论这是否算作子类型,它都可以用于此目的。 - Ørjan Johansen
显示剩余2条评论
5个回答

16
在带类型的 lambda 演算中,我们有类型关系,通常表示为 : 或在 Haskell 中表示为 ::。一般来说,该关系是“多对多”的,因此一个类型可以包含多个值,一个值也可以有多个类型。
特别地,在多态类型系统中,一个值可以有多个类型。例如:
map :: (a -> b) -> [a] -> [b]

但也

map :: (Int -> Int) -> [Int] -> [Int].

在这种类型系统中,有时可以定义一种关于类型的关系,其含义为“比某个类型更一般”,即type order。如果t ⊑ s,则ts更一般,意味着如果M : t,那么也必定M : s,而此类类型系统的类型规则正是允许推断出这一点。或者说st的一种特化。因此,在这种意义下,类型之间存在subtyping关系。
然而,当我们谈论面向对象语言中的子类型时,通常指的是nominal subtyping,即我们会声明哪些类型是什么类型的子类型,就像定义类继承一样。而在Haskell中,这是类型的一个属性,独立于任何声明。例如,任何类型都是forall a . a的一种特化。

对于Hindley-Milner类型系统,它允许类型推断并且是大多数函数式语言的基础,有主类型的概念:如果一个表达式M有一个(任意)类型,那么它也有其主类型,并且主类型是所有可能类型中最通用的类型。关键特征是HM类型推断算法总是找到最通用的类型。因此,可以将最通用、推断出的主类型专门化为M的任何有效类型。


“t ⊑ s” 不是表示 “t” 比 “s” 更一般,而是表示 “t” 比 “s” 更具体吗? - dfeuer
@dfeuer 我使用了与维基百科HM页面相同的表示法,其中 ⊑ 表示“比...更一般”。可能该页面是错误的 :). - Petr
你还写道“这意味着如果 M : t,那么也有 M : s”,但这似乎不太匹配。不过我可能错了。 - dfeuer
1
据我理解,如果t更通用,则其取值范围更小(这可能是⊑的原因)。 因此,如果M:tst的特化,则也有M:s - Petr
嗯,是的,那可能就是了。我知道如何正确使用这些关系,但我不知道如何恰当地命名它们。 - dfeuer

11
对于这样的问题,我会退一步并说,从根本上讲,Haskell设计背后的数学理论是不具有子类型概念的System F变体。
是的,可能可以看到Haskell的表面语法存在像您提出的那种情况,其中某些类型为T的表达式可以在任何期望T'的上下文中使用。但这并不是因为Haskell被设计支持子类型而出现的。相反,它是由于Haskell被设计为比对System F的忠实呈现更加用户友好而产生的偶然性。
在这种情况下,这与类型级量化器通常不会在Haskell代码中显式编写有关,而类型级lambda和应用程序从不在其中。如果从System F角度看待类型forall a. a,则其替代到Int上下文中就消失了。 a :: forall a. a是一个类型级函数,不能在期望Int的上下文中使用-您需要首先将其应用于Int以获得a Int :: Int,然后才能在Int上下文中实际使用它。 Haskell的语法隐藏了这一点,以追求用户友好性,但是在基础理论中确实存在。
因此简而言之,虽然您可以通过制表来分析Haskell,确定哪些表达式类型可以替换为哪些上下文类型,并证明存在某种加密子类型关系,但这并不是有成果的,因为它产生的分析与设计背道而驰。这不仅仅是技术细节的问题,更是意图和其他人类因素的问题。

1
值得注意的是,一些多态类型系统的形式化(即Haskell的近亲)实际上将更多态关系建模为子类型的一种形式。请参见我的答案以获取示例参考。 - Dominique Devriese
虽然 GHC 使用 System F 变体作为其基础理论,但这似乎并不固有于 Haskell 类型系统。我想知道 @DominiqueDevriese 提到的那些理论是否可以代替使用。 - dfeuer
@dfeuer “核心语言”有两种类型(“将类型注释付诸实践”中的一种和GHC的System F扩展),它们的范围/目的不同。前者包括一种类型推断形式,因为例如,类型为forall a. a的值可以用在需要Int的地方。 GHC的System F后代需要显式类型应用程序来将forall a. a值转换为Int。仅当类型推断首先添加了必要的类型应用/抽象时,该语言才会对Haskell进行建模。我想,未对类型推断进行建模既是优点也是缺点,这取决于应用程序。 - Dominique Devriese

5
您是正确的,类型为forall a. a的值可以用在期望Int的任何地方,这意味着这两种类型之间存在一个子类型关系。其他回答试图让您相信这种“更多态性”的关系不是子类型。然而,虽然它肯定不同于典型面向对象语言中发现的子类型形式,但这并不意味着“更多态性”的关系不能被看作是一种(不同的)子类型形式。实际上,在一些多态类型系统的形式化模型中,正好将此关系建模为其子类型关系。例如,在Odersky和Läufer的论文“Putting type annotations to work”中的类型系统中就是这种情况。

我认为称其为子类型是具有误导性的。它并不是真正意义上的面向对象编程风格的子类型。尽管那篇论文确实很有趣。 - AJF
我不同意:关键在于子类型化不仅仅是面向对象编程风格的子类型化。 - Dominique Devriese

3

:: a表示“任何类型”,但不是子类型。 a可能是IntBoolIO (Maybe Ordering),但没有特定的类型。 a不是一个确切的类型,而是一个类型变量。

假设我们有一个如下所示的函数:

id x = x

编译器知道我们的参数x没有特定的类型。我们可以使用任何类型进行x,只要它等同于id的输出。因此,我们将签名编写为:
--    /- Any type in...
--    |    /- ...same type out.
--    V    V
id :: a -> a

请记住,Haskell中类型以大写字母开头。这不是一个类型:它是一个类型变量!

我们使用多态是因为这样更容易。比如,组合是一个有用的想法:

(>>>) :: (a -> b) -> (b -> c) -> (a -> c)
(>>>) f g a = g (f a)

因此,我们可以编写以下内容:

plusOneTimesFive :: Int -> Int
plusOneTimesFive = (+1) >>> (* 5)

reverseHead :: [Bool] -> Bool
reverseHead = reverse >>> head

但是如果我们必须像这样写出每种类型会怎么样呢:

(>>>) :: (Bool -> Int) -> (Int -> String) -> (Bool -> String)
(>>>) f g a = g (f a)

(>>>') :: (Ordering -> Double) -> (Double -> IO ()) -> (Ordering -> IO ())
(>>>') f g a = g (f a)

(>>>'') :: (Int -> Int) -> (Int -> Bool) -> (Int -> Bool)
(>>>'') f g a = g (f a)

-- ...and so on.

那只是愚蠢的事情。

因此,编译器使用类型统一来推断类型,就像这样:

假设我将以下内容输入GHCi。在这里为了简单起见,假设6Int

id 6

编译器认为:“id :: a -> a”,并且传入了一个Int,所以a = Int,因此id 6 :: Int
这不是子类型。子类型可以使用类型类来捕获,但这是基本的多态性在起作用。

1
我认为你错了,这是子类型化。请看下面我的回答。 - Dominique Devriese

2

这不是子类型,而是类型统一!

a :: forall a. a
a = undefined

b :: Int
b = a

b = a中,我们限制ba必须是相同的类型,因此编译器检查是否可能。 a的类型为forall a. a,根据定义,可以与任何类型统一,因此编译器允许我们的约束条件。
类型统一还使我们能够做以下事情:
f :: (a -> Int) -> a
g :: (String -> b) -> b
h :: String -> Int
h = f g

穿过统一,f :: (a -> Int) -> a 表示 g 必须具有类型 a -> Int,这意味着 a -> Int 必须与 (String -> b) -> b 统一,因此 b 必须是 Int,这给出了 g 的具体类型 (String -> Int) -> Int,这意味着 aString -> Inta -> Int(String -> b) -> b 都不是对方的子类型,但它们可以作为 (String -> Int) -> Int 统一。

我不明白这个答案如何回答问题:“为什么forall a. a不被视为Int的子类型?” - Dominique Devriese
3
主要原因是它不是一种类型? - Cubic
1
@Cubic: 什么不是类型?forall a. aInt 明显都是类型,对吧? - Dominique Devriese
除了类型之外,它还能是什么? - dfeuer

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接