柯里化的前生今世(十二):多态性

  1. 云栖社区>
  2. 博客>
  3. 正文

柯里化的前生今世(十二):多态性

何幻 2016-10-28 17:51:05 浏览1229
展开阅读全文

关于

本文借用Haskell介绍了自定义类型,带参数的类型,Ad-hoc多态性,kind,
其中,带参数的类型在类型上可以做“柯里化”。

1. 自定义类型

Haskell中使用data自定义类型。

data Bool = True | False

其中,Bool是类型名,TrueFalse是该类型的值。

一个值可以包含多种不同类型的字段(field),例如,

data BookType = BookValue Int String

其中BookType是类型名,BookValue是值构造器(Value constructor)。
一个BookType类型的值,可以这样定义,

bookValue = BookValue 12 "ab"

注:
类型名和值构造器会在不同上下文中使用,
因此,常把它们写成同一个名字,应当注意区分。

data Book = Book Int String

2. 抽象与具体化

lengthInt :: [Int] -> Int
lengthInt [] = 0
lengthInt (_:xs) = 1 + lengthInt xs

lengthChar :: [Char] -> Int
lengthChar [] = 0
lengthChar (_:xs) = 1 + lengthChar xs

lengthIntlengthChar虽然类型不同,但是计算过程相同,
如果我们想计算不同类型列表的长度,就需要写多个不同的函数,
这违背了软件工程中基本的设计原则:

Abstraction principle:
Each significant piece of functionality in a program should be implemented in just one place in the source code. Where similar functions are carried out by distinct pieces of code, it is generally beneficial to combine them into one by abstracting out the varying parts.

和通常的代码不同,这里提到的varying parts指的是类型,
我们需要提取出一个抽象的类型[a]
然后再实例化为不同的具体类型[Int][Char]

3. 多态类型系统

Type systems that allow a single piece of code to be used with multiple types are collectively known as polymorphic systems (poly = many, morph = form).

如果一个类型系统,允许一段代码在不同的上下文中具有不同的类型,
这样的类型系统就称为多态类型系统。

现代编程语言,包含了不同形式的多态性:
参数化多态,Ad-hoc多态,子类型多态。

(1)参数化多态(Parametric polymorphism)

data Maybe a = Just a | Nothing

以上代码定义了一个带参数的类型Maybe,它不能表示某个值的类型,
Maybe Int放在一起,才是一个具体的类型,
类型名Maybe也称为类型构造器(Type constructor)。

length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs

如果某个函数(函数是一种值)的类型是一个带参数的类型,
函数的计算过程就可以写到一个地方,
不同的调用场景,会将length函数具体化为不同的类型。

length [1,2,3]length被具体化为[Int] -> Int
length ['a','b','c']length被具体化为[Char] -> Char

(2)Ad-hoc多态(Ad-hoc polymorphism)

某个Ad-hoc多态类型的值,看做不同类型时,会有不同的行为。
重载(Overloading)就是一种Ad-hoc多态,
它可以让一个函数具有不同的实现。
每次函数调用,编译器(或运行时系统)会选择适当的实现。

class BasicEq a where 
    isEqual :: a -> a -> Bool

instance BasicEq Bool where 
    isEqual True True = True 
    isEqual False False = True 
    isEqual _ _ = False

Haskell中的typeclass使用了Ad-hoc多态,
函数isEqual在具体化为不同的类型时,可以有不同的实现。

(3)子类型多态(Subtype polymorphism)

它允许某个类型的值,在包含关系上,可以看做它也是父类型的值。
在面向对象语言社区,经常把子类型多态,简称为多态。

注:
同一种语言可能具有不同的多态性,
例如,Standard ML提供了参数化多态,内置运算符重载(Ad-hoc多态),
但是没有提供子类型多态。
而Java提供了子类型多态,函数重载(Ad-hoc多态),泛型(参数化多态)。

4. kind

关于带参数的类型,
与函数Currying相似,类型构造器也可以“Currying”,
例如,我们定义以下带两个参数的Either类型,

data Either a b = Left a | Right b

其中Either是一个类型构造器,接受两个类型参数IntString
得到具体类型Either Int String

如果只提供一个类型参数呢?
Either Int仍然是一个类型构造器,它接受一个类型参数String
得到具体类型Either Int String

正因为有这种差异性,
Haskell中使用kind来区分不同的类型。

ghci> :k Int
Int :: *

ghci> :k Maybe
Maybe :: * -> *

ghci> :k Maybe Int
Maybe Int :: *

ghci> :k Either
Either :: * -> * -> *

ghci> :k Either Int
Either Int :: * -> *

ghci> :k Either Int String
Either Int String :: *

5. >>=的多态性

函数>>=定义在Monad typeclass中,

class Monad m where
    (>>=) :: m a -> (a -> m b) -> m b

其中,mMonad typeclass的实例类型,它的kind* -> *
类型m a是一个具体类型,该类型的值称为monad value。

我们看到,在m确定的情况下,>>=的类型签名中仍然包含类型变量。
因此,对于Monad typeclass的某个实例来说,
>>=可以操作相同m类型但是不同a类型的monad value :: m a

Monad typeclass的实例IO为例,对于IO来说,IO monad value称为IO action。

main :: IO ( )
main = do
    putStrLn "Please input: "
    inpStr <- getLine
    putStrLn $ "Hello " ++ inpStr

其中,putStrLn :: String -> IO ( )getLine :: IO String

我们来分析一下这3个IO action的类型吧,

putStrLn "Please input: " :: IO ( )
getLine :: IO String
putStrLn $ "Hello " ++ inpStr :: IO ( )

它们的具体类型都是m a
m相同,m = IO
a不同,分别是( )String( )

我们知道do notation是>>=的语法糖,我们将do notation转换成>>=的串联形式,

(putStrLn "Please input: ") >>= (\ _ -> (getLine >>= (\inpStr -> (putStrLn $ "Hello " ++ inpStr ))))

对于第一个>>=,我们能推断出它的大概类型,

>>= :: IO ( ) -> (( ) -> IO ?) -> IO ?

其中“?”表示尚未确定的类型。

而第二个>>=的类型,可以完全确定下来。

>>= :: IO String -> (String -> IO ( )) -> IO ( )

最后,第一个>>=的类型也就可以完全确定下来了,

>>= :: IO ( ) -> (( ) -> IO ( )) -> IO ( )

由此可见,
第一个>>= :: IO ( ) -> (( ) -> IO ( )) -> IO ( )
第二个>>= :: IO String -> (String -> IO ( )) -> IO ( )
两个>>=的类型不同,它们同时出现了。

因此,在参数化类型中,类型变量的解和数学方程中未知数的解,意义不同,
在数学方程中,同名未知数对应相同的解,
而在不同的程序上下文中,同名类型变量可以被确定为不同的具体类型。

当类型具有多态性时,为了让整个程序类型合法,
类型变量就必须满足各个表达式的类型约束条件(constraints),
只不过,不同位置的类型变量取值可以不同。

>>=的定义中包含了参量mab

(>>=) :: m a -> (a -> m b) -> m b

在同一个程序中,m确定为IOa在有的地方确定为( ),有的地方确定为String

确定这些类型变量的过程,称为类型重建(type reconstruction),
有时也称为类型推导(type inference)。

6. 1 :: Num a => a

我们来看看1的类型

ghci> :t 1
1 :: Num a => a

这说明1具有Ad-hoc多态性,它是Num typeclass中定义的值。

在使用Haskell的typeclass时,如果和面向对象语言中的interface类比,
就很容易产生一个误区,认为typeclass中只能定义函数。
而实际上,typeclass中定义了一些具有Ad-hoc多态类型的值。
这个值,当然可以是函数类型的。

例如:

class TypeClassWithValue t where 
    plainValue :: t 
    functionValue :: t -> t

我们来检测下:

ghci> :t plainValue
plainValue :: TypeClassWithValue t => t

ghci> :t functionValue
functionValue :: TypeClassWithValue t => t -> t

注:
在Haskell规范中并不是这样解释字面量1的,

An integer literal represents the application of the function fromInteger to the appropriate value of type Integer.

其中fromInteger :: (Num a) => Integer -> a
因此,整数字面量的类型就是(Num a) => a了。

整数字面量之所以用这种间接的方式来定义,
是为了让它们具有Ad-hoc多态性,
可以在Num typeclass不同的实例类型中使用它们。

7. 参考:

Polymorphism)
Types and Programming Languages
Haskell 2010 Language Report

网友评论

登录后评论
0/500
评论
何幻
+ 关注