多态:以 Haskell 为例

一般地来说,一个值,或者说一个函数,是多态的,当它可以是多种类型的。Haskell原始支持的多态分为参数多态和 ad-hoc 多态。
在文章haskell学习笔记中提到了Parametric polymorphism、higher kinded polymorphism 和 higher rank polymorphism三个概念,我们将在本文中详细探讨。

参数多态和Ad-hoc多态

参数多态

参数多态(Parametric polymorphism)类似于其他语言中的泛型或者模板,此时一个值的类型中包含多个(unconstrained) type variable。

1
2
id :: a -> a
id x = x
1
2
3
4
template <typename T>
auto id(T x){
return x;
}

在上面的代码中,a称为(unconstrained) type variable,它可以是任意的,这体现在没有=>这样typeclass的约束。因此这也隐含了对于不同的类型,多态值的行为都是一致的,这是因为parametrically polymorphic value本身对自己的type variable类型一无所知。

Ad-hoc多态

相对应地,Ad-hoc显得更随机应变。此时,这个多态值可以采用若干类型其中的一个,每一种不同类型的行为都是不同的。例如对于(+),它对浮点数的处理和对整数的处理显然是不一样的。
特别地,typeclass中定义的函数也可以是类型多态或 Ad-hoc 多态的,这在文章haskell学习笔记的Ch3有详细探讨。

子类多态

Haskell 并没有提供子类多态的性质。子类多态实际上是类似 Protocol、Interface、Inherit 这样的东西。

Rank N多态

定义

Universal quantification表示对于任意的,即∀。Haskell 中有对应的关键字 forall。如下所示,在使用支持了 Existential Quantification 扩展的 Haskell 时,查看 map 的定义

1
map :: forall a b. (a -> b) -> [a] -> [b]

在 Haskell 98 中,像上面 a 和 b 这样的 free variable 是 implicitly universally quantified 的。在 Haskell 98 中只允许 Rank 1 Type,也就是说 Type 具有下面的形式:

  1. type -> type
  2. forall vars. [context =>] type
  3. monotype
    也就是 Haskell 98 type

Note that forall‘s are not allowed inside type constructors other than ->.

foralls and contexts in the second argument of -> may be floated out。如下所示,后面的 forall b 可以被提出来

1
2
succ :: (forall a. a -> a) -> (forall b. b -> b)
succ :: forall b. (forall a. a -> a) -> b -> b

但在 Higher Rank Types 中,type annotations 往往是不能被省略的。

Rank 1

Haskell 中的 Rank N Types 模块实现了 higher rank polymorphism 的概念。
首先研究什么是 Rank 1。

1
2
3
{-# LANGUAGE RankNTypes #-}

id :: forall a. a -> a

引入的 forall 显式说明 id 能够作用在任意的(universally quantified)类型上。

通过 let 或者 where 绑定的变量可以是 polymorphic 的。如下所示,f 既可以对 True 应用,又可以对 Char 应用,它肯定是个 Rank 2 了

1
2
> let f x = x in (f True, f 'a')
(True,'a')

但 Haskell 不允许一个函数作为参数是 polymorphic 的。例如下面的语句不能编译

1
g f = (f True, f 'a')

但在 Rank 2 特性下,g 就可以有下面的签名了

1
g :: (forall a. a -> a) -> (Bool, Char)

Rank 2

接下来是 Rank 2。

1
2
3
type IdFunc = forall a. a -> a
id :: IdFunc
id x = x

在上面的代码中,我们为 forall a. a -> a 这样类型的函数创建了一个 alias,称为 IdFunc。然后定义了一个 IdFunc 类型的函数 id。在这一步中,type variable a 消失了。紧接着我们又定义 someInt 这个函数,它是 monomorphic 的,虽然它接受一个 polymorphic 的参数。

1
2
someInt :: IdFunc -> Integer
someInt id' = id' 3

进一步看函数 someInt,它要求传入一个多态函数,但自己却是单态的。这样的函数在原始 Haskell 中是不允许的,支持它们会给类型推导带来困难。

从另一个角度查看这个问题,

1
a -> b -> a

上面的 type signature 隐含了 ab 这两个 type variable 是 universally quantified 的,因此可以被写作

1
forall a b. a -> b -> a

forall关键字可以被提到 (->) 的右边,或者 (->) 右边的 forall 可以提到前面,正如(->)是右结合的。即下面的形式也是 Rank-1 的,并且与上面的写法都等价

1
forall a. a -> (forall b. b -> a)

但是在某一个 (->) 左边的 forall 不可以被提出。下面的语句中,后面的 forall 可以被提到最前面,因为它在 (->) 的右边;而前面的 forall 则不能提到最前面。

1
(forall a. a -> a) -> (forall b. b -> b)

我们发现在上面的语句中出现了两个层面的universal quantification,forall b能够被提到最前面,适用范围更广一点。这样的类型就是Rank-2的。

1
2
3
4
5
6
Prelude> f :: (forall a. a -> a) -> (forall b. b -> b)

<interactive>:3:15:
Illegal symbol '.' in type
Perhaps you intended to use RankNTypes or a similar language
extension to enable explicit-forall syntax: forall <tvs>. <type>

类型多态

在先前,我们讲到的“函数”都是关乎值的,而类型多态,也就是 higher kinded polymorphic,可以看做类型和类型之间的函数。

Reference

  1. https://ocharles.org.uk/blog/guest-posts/2014-12-18-rank-n-types.html
  2. https://www.stephanboyer.com/post/115/higher-rank-and-higher-kinded-types
  3. https://wiki.haskell.org/Rank-N_types
  4. https://wiki.haskell.org/Polymorphism
  5. https://www.haskell.org/hugs/pages/users_guide/quantified-types.html
  6. https://gitlab.haskell.org/haskell/prime/-/wikis/RankNTypes