柯里化的前生今世（十二）：多態性

03-07

關於

本文借用Haskell介紹了自定義類型，帶參數的類型，Ad-hoc多態性，kind，

其中，帶參數的類型在類型上可以做「柯里化」。

1. 自定義類型

Haskell中使用data自定義類型。

data Bool = True | False

其中，Bool是類型名，True和False是該類型的值。

一個值可以包含多種不同類型的欄位（field），例如，

data BookType = BookValue Int String

其中BookType是類型名，BookValue是值構造器（Value constructor）。

一個BookType類型的值，可以這樣定義，

bookValue = BookValue 12 "ab"

註：

類型名和值構造器會在不同上下文中使用，

因此，常把它們寫成同一個名字，應當注意區分。

data Book = Book Int String

2. 抽象與具體化

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

lengthInt和lengthChar雖然類型不同，但是計算過程相同，

如果我們想計算不同類型列表的長度，就需要寫多個不同的函數，

這違背了軟體工程中基本的設計原則：

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] -> Intlength [] = 0length (_: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 -> Boolinstance 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是一個類型構造器，接受兩個類型參數Int和String，

得到具體類型Either Int String。

如果只提供一個類型參數呢？

Either Int仍然是一個類型構造器，它接受一個類型參數String，

得到具體類型Either Int String。

正因為有這種差異性，

Haskell中使用kind來區分不同的類型。

ghci> :k IntInt :: *ghci> :k MaybeMaybe :: * -> *ghci> :k Maybe IntMaybe Int :: *ghci> :k EitherEither :: * -> * -> *ghci> :k Either IntEither Int :: * -> *ghci> :k Either Int StringEither Int String :: *

5. `>>=`的多態性

函數>>=定義在Monad typeclass中，

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

其中，m是Monad 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 StringputStrLn $ "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），

只不過，不同位置的類型變數取值可以不同。

>>=的定義中包含了參量m，a和b，

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

在同一個程序中，m確定為IO，a在有的地方確定為( )，有的地方確定為String。

確定這些類型變數的過程，稱為類型重建（type reconstruction），

有時也稱為類型推導（type inference）。

6. `1 :: Num a => a`

我們來看看1的類型

ghci> :t 11 :: 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 plainValueplainValue :: TypeClassWithValue t => tghci> :t functionValuefunctionValue :: 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不同的實例類型中使用它們。

參考

Polymorphism

Types and Programming Languages

Haskell 2010 Language Report