为什么是forall一个。 a 不被认为是 Int 的子类型,而我可以使用类型为 forall a 的表达式。期望 Int 类型的任何地方?
Why is forall a. a not considered a subtype of Int while I can use an expression of type forall a. a anywhere one of type Int is expected?
考虑以下一对函数定义,它们通过了类型检查器:
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
这不是子类型化,而是 type unification!
a :: forall a. a
a = undefined
b :: Int
b = a
在 b = a
中,我们将 b
和 a
限制为同一类型,因此编译器会检查这是否可行。 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
must b
must be Int
,这给了 g
具体类型 (String -> Int) -> Int
,这意味着 a
是 String -> Int
.
a -> Int
和(String -> b) -> b
都不是对方的子类型,但可以统一为(String -> Int) -> Int
。
:: a
是指 "Any type",但不是子类型。 a
可以 Int
,或Bool
,或IO (Maybe Ordering)
,但特别是none。 a
不完全是类型,而是类型变量。
假设我们有这样一个函数:
id x = x
编译器理解我们的参数没有特定类型x
。我们可以对 x
使用 any 类型,只要它等同于 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 中。为简单起见,我们在 Int
中说 6
。
id 6
编译器认为:“id :: a -> a
,它被传递给 Int
,所以 a = Int
,所以 id 6 :: Int
。
这是不是子类型。可以使用类型类捕获子类型,但这是基本的多态性。
对于这样的问题,我会退后一步说,从根本上说,构成 Haskell 设计基础的数学理论是 System F 没有概念的变体分型。
是的,可以查看 Haskell 的表面语法并注意存在像您提出的情况,其中某种类型的表达式 T
可以用于任何预期 T'
的上下文。但这不会出现,因为 Haskell 旨在支持子类型。相反,它的出现是因为 Haskell 被设计成比系统 F 的忠实呈现更加用户友好的事实。
在这种情况下,它与以下事实有关:类型级量词通常不会在 Haskell 代码中显式编写,并且类型级 lambda 和应用程序 never 是。如果您从系统 F 的角度来看 forall a. a
类型,那么 Int
上下文的可替换性就会消失。 a :: forall a. a
是一个类型级别的函数,不能在需要 Int
的上下文中使用——您需要先将它应用到 Int
以获得 a Int :: Int
,这就是您想要的实际上可以在 Int
上下文中使用。 Haskell 的语法以用户友好的名义隐藏了这一点,但它存在于基础理论中。
所以简而言之,虽然您可以通过列出哪些表达式类型可以替换为哪些上下文类型来分析 Haskell 并证明存在某种加密子类型关系,但它并不富有成效,因为它会产生分析逆流而上的设计。这与其说是技术问题,不如说是意图和其他人为因素。
你是正确的,类型 forall a. a
的值可以用在任何需要 Int
的地方,这意味着两种类型之间存在子类型关系。上面的其他答案试图让你相信这个 "more-polymorphic-than" 关系不是子类型。然而,虽然它肯定不同于典型的面向对象语言中的子类型化形式,但这并不意味着 "more-polymorphic-than"-关系不能被视为一种(不同的)子类型化形式。事实上,一些多态类型系统的形式化在它们的子类型关系中精确地模拟了这种关系。例如,Odersky 和 Läufer 的论文 "Putting type annotations to work".
中的类型系统就是这种情况。
在类型化 lambda 演算中,我们有类型关系,通常表示为 :
或在 Haskell 中表示为 ::
。一般来说,关系是"many to many",所以一个类型可以包含多个值,一个值也可以有多个类型。
特别是在多态类型系统中,一个值可以有多种类型。例如
map :: (a -> b) -> [a] -> [b]
还有
map :: (Int -> Int) -> [Int] -> [Int].
在这样的类型系统中,(有时)可以定义类型关系,其含义为 "more general type than",type order. If t ⊑ s
then t
is more general than s
, meaning that if M : t
then also M : s
, and the typing rules of such a type system allow to infer exactly that. Or we say that s
is a specialization of t
. So in this sense, there is a subtyping 类型关系。
然而,当我们在面向对象语言中谈论子类型时,我们通常指的是 nominal subtyping,也就是说,我们 声明 哪些类型是什么的子类型,比如什么时候我们定义 class 继承。而在 Haskell 中,它是一个 属性 类型,独立于任何声明。例如,任何类型都是 forall a . a
.
的特化
对于Hindley-Milner type system, which allows type inference and which is the base for most functional languages, there is the notion of principal type:如果表达式M
有一个(任何)类型,那么它也有它的主要类型,主要类型是所有可能类型中最一般的类型M
。关键特性是 HM 类型推理算法总能找到最通用的类型。因此,最一般的推断主体类型可以专门化为 M
.
的任何有效类型
考虑以下一对函数定义,它们通过了类型检查器:
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
这不是子类型化,而是 type unification!
a :: forall a. a
a = undefined
b :: Int
b = a
在 b = a
中,我们将 b
和 a
限制为同一类型,因此编译器会检查这是否可行。 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
must b
must be Int
,这给了 g
具体类型 (String -> Int) -> Int
,这意味着 a
是 String -> Int
.
a -> Int
和(String -> b) -> b
都不是对方的子类型,但可以统一为(String -> Int) -> Int
。
:: a
是指 "Any type",但不是子类型。 a
可以 Int
,或Bool
,或IO (Maybe Ordering)
,但特别是none。 a
不完全是类型,而是类型变量。
假设我们有这样一个函数:
id x = x
编译器理解我们的参数没有特定类型x
。我们可以对 x
使用 any 类型,只要它等同于 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 中。为简单起见,我们在 Int
中说 6
。
id 6
编译器认为:“id :: a -> a
,它被传递给 Int
,所以 a = Int
,所以 id 6 :: Int
。
这是不是子类型。可以使用类型类捕获子类型,但这是基本的多态性。
对于这样的问题,我会退后一步说,从根本上说,构成 Haskell 设计基础的数学理论是 System F 没有概念的变体分型。
是的,可以查看 Haskell 的表面语法并注意存在像您提出的情况,其中某种类型的表达式 T
可以用于任何预期 T'
的上下文。但这不会出现,因为 Haskell 旨在支持子类型。相反,它的出现是因为 Haskell 被设计成比系统 F 的忠实呈现更加用户友好的事实。
在这种情况下,它与以下事实有关:类型级量词通常不会在 Haskell 代码中显式编写,并且类型级 lambda 和应用程序 never 是。如果您从系统 F 的角度来看 forall a. a
类型,那么 Int
上下文的可替换性就会消失。 a :: forall a. a
是一个类型级别的函数,不能在需要 Int
的上下文中使用——您需要先将它应用到 Int
以获得 a Int :: Int
,这就是您想要的实际上可以在 Int
上下文中使用。 Haskell 的语法以用户友好的名义隐藏了这一点,但它存在于基础理论中。
所以简而言之,虽然您可以通过列出哪些表达式类型可以替换为哪些上下文类型来分析 Haskell 并证明存在某种加密子类型关系,但它并不富有成效,因为它会产生分析逆流而上的设计。这与其说是技术问题,不如说是意图和其他人为因素。
你是正确的,类型 forall a. a
的值可以用在任何需要 Int
的地方,这意味着两种类型之间存在子类型关系。上面的其他答案试图让你相信这个 "more-polymorphic-than" 关系不是子类型。然而,虽然它肯定不同于典型的面向对象语言中的子类型化形式,但这并不意味着 "more-polymorphic-than"-关系不能被视为一种(不同的)子类型化形式。事实上,一些多态类型系统的形式化在它们的子类型关系中精确地模拟了这种关系。例如,Odersky 和 Läufer 的论文 "Putting type annotations to work".
在类型化 lambda 演算中,我们有类型关系,通常表示为 :
或在 Haskell 中表示为 ::
。一般来说,关系是"many to many",所以一个类型可以包含多个值,一个值也可以有多个类型。
特别是在多态类型系统中,一个值可以有多种类型。例如
map :: (a -> b) -> [a] -> [b]
还有
map :: (Int -> Int) -> [Int] -> [Int].
在这样的类型系统中,(有时)可以定义类型关系,其含义为 "more general type than",type order. If t ⊑ s
then t
is more general than s
, meaning that if M : t
then also M : s
, and the typing rules of such a type system allow to infer exactly that. Or we say that s
is a specialization of t
. So in this sense, there is a subtyping 类型关系。
然而,当我们在面向对象语言中谈论子类型时,我们通常指的是 nominal subtyping,也就是说,我们 声明 哪些类型是什么的子类型,比如什么时候我们定义 class 继承。而在 Haskell 中,它是一个 属性 类型,独立于任何声明。例如,任何类型都是 forall a . a
.
对于Hindley-Milner type system, which allows type inference and which is the base for most functional languages, there is the notion of principal type:如果表达式M
有一个(任何)类型,那么它也有它的主要类型,主要类型是所有可能类型中最一般的类型M
。关键特性是 HM 类型推理算法总能找到最通用的类型。因此,最一般的推断主体类型可以专门化为 M
.