Haskell 类型系统进阶

「和」：乘积类型

基本上所有的编程语言都有乘积类型，可以组合类型，比如 C 语言的 struct：

struct author_name {
  char* first_name;
  char* last_name;
}

struct book {
  author_name author;
  char* isbn;
  char* title;
  int year_published;
  double price;
};

翻译成 Haskell 就是：

type FirstName = String

type LastName = String

data AuthorName = AuthorName FirstName LastName deriving (Show)

data Book = Book
  { author :: AuthorName,
    isbn :: String,
    title :: String,
    year :: Int,
    price :: Double
  }

这就是编程语言中 继承 的基础。可以抽离公共部分，完成层级的设计。

「或」：加法类型

这是个强大的工具。有很多例子都可以用「或」来建模：

• 骰子可能是 6 面的或者是 20 面的
• 论文的作者可能是 1 String 或者多个 [String]

最直接的是 Bool。

data Bool = False | True

半群和幺半群

组合函数

一个特殊的高阶函数只是一个句点 .（称为 compose），她接受两个函数作为参数，动态组合函数。

import Data.List (sort)

myLast :: Ord a => [a] -> a
myLast = head . reverse

myMin :: Ord a => [a] -> a
myMin = head . sort

myMax :: Ord a => [a] -> a
myMax = myLast . sort

ghci> myMin [3, 2, 10, 1, -1]
-1
ghci> myLast [2, 3, 0, 1]
1
ghci> myMax [3, 2, 10, 1, -1]
10

半群 Semigroups

数学上半群的要求条件非常简单，只需要满足结合性即可，所以只需要实现 <> 即可。

考虑一个颜色的组合（结合）：

data Color = Red | Yellow | Blue | Green | Purple | Orange | Brown deriving (Show, Eq)

instance Semigroup Color where
  (<>) Red Blue = Purple
  (<>) Blue Red = Purple
  (<>) Yellow Blue = Green
  (<>) Blue Yellow = Green
  (<>) Yellow Red = Orange
  (<>) Red Yellow = Orange
  (<>) a b | a == b = a
    if a == b
      then a
      else Brown

ghci> Red <> Yellow
Orange
ghci> Red <> Blue
Purple

由于半群满足结合性，所以可以进行多个的组合：

ghci> (Green <> Blue) <> Yellow
Brown
ghci> Green <> (Blue <> Yellow)
Green

但这个结果看起来是有点奇怪的。可以考虑使用 守卫 （guard）语法来补充一些定义：

instance Semigroup Color where
  (<>) Red Blue = Purple
  (<>) Blue Red = Purple
  (<>) Yellow Blue = Green
  (<>) Blue Yellow = Green
  (<>) Yellow Red = Orange
  (<>) Red Yellow = Orange
  (<>) a b
    | a == b = a
    | all (`elem` [Red, Blue, Purple]) [a, b] = Purple
    | all (`elem` [Blue, Yellow, Green]) [a, b] = Green
    | all (`elem` [Red, Yellow, Orange]) [a, b] = Orange
    | otherwise = Brown

ghci> (Green <> Blue) <> Yellow
Green
ghci> Green <> (Blue <> Yellow)
Green

| 很类似其它语言中的 if 的条件分支。

幺半群

幺半群（Monoids）比半群多了一个条件，就是要求有单位元。幺半群的元素与单位元 id 进行运算后保持不变，即 x <> id = x（也包括 id <> x = x）。对于整数的加法来讲，单位元就是 0。

class Semigroup a => Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a

考虑用幺半群做一个概率表。如果有一枚硬币，那么正反面的概率都是 0.5，概率表如下：

用 Haskell 代码表述就是：

type Events = [String]
type Probs = [Double]

data PTable = PTable Events Probs

现在做一个构造函数，同时对概率进行归一化处理，确保概率之和等于 1：

createPTable :: Events -> Probs -> PTable
createPTable events probs = PTable events normalizedProbs
  where
    totalProbs = sum probs
    normalizedProbs = map (\x -> x / totalProbs) probs

实现一个函数，用于输出概率表一行的字符串：

showPair :: String -> Double -> String
showPair event prob = mconcat [event, "|", show prob, "\n"]

mconcat 提供了更抽象化的连接，而不像 ++ 局限在字符串上。为了实现打印概率表，需要实现 Show：

instance Show PTable where
  show (PTable events probs) = mconcat pairs
    where
      pairs = zipWith showPair events probs

zipWith 是一个高阶函数，它将一个函数和两个列表作为参数，并返回一个新的列表，其中每个元素是由应用该函数于两个输入列表相应位置的元素所得的结果。

ghci> zipWith (+) [1,2,3] [4,5,6]
[5,7,9]

所以，zipWith 将事件和概率一一配对后，经过 showPair 最后成为一个字符串列表，再最后通过 mconcat 组合成字符串。

这样就可以创建概率表了：

ghci> createPTable ["head", "tails"] [0.5, 0.5]
head|0.5
tails|0.5

如果是多个硬币，那么概率的结果就应该是一个笛卡尔积。所以我们创建一个生成笛卡尔积的函数：

cartCombine :: (a -> b -> c) -> [a] -> [b] -> [c]
cartCombine func l1 l2 = zipWith func newL1 cycledL2
  where
    nToAdd = length l2
    repeatedL1 = map (take nToAdd . repeat) l1
    newL1 = mconcat repeatedL1
    cycledL2 = cycle l2

这个 cartCombine 函数的作用是生成两个列表的笛卡尔积(Cartesian product)。它接受一个二元函数 func 和两个列表 l1、l2 作为输入，将 func 应用于 l1 和 l2 的每对元素组合，生成一个新的列表 [c]。

之后就可以用 cartCombine 来组合事件和概率：

combineEvents :: Events -> Events -> Events
combineEvents e1 e2 = cartCombine combiner e1 e2
  where
    combiner = (\x y -> mconcat [x, " - ", y])

combineProbs :: Probs -> Probs -> Probs
combineProbs p1 p2 = cartCombine (*) p1 p2

有了这两个方法，就可以将 PTable 做成半群的实例：

instance Semigroup PTable where
  (<>) ptable1 (PTable [] []) = ptable1
  (<>) (PTable [] []) ptable2 = ptable2
  (<>) (PTable e1 p1) (PTable e2 p2) = createPTable newEvents newProbs
    where
      newEvents = combineEvents e1 e2
      newProbs = combineProbs p1 p2

有了半群，那么我们只需要有单位元就可以变成幺半群了，因为幺半群的连接操作和半群是一样的。

instance Monoid PTable where
  mempty = PTable [] []
  mappend = (<>)

现在我们就拥有了可以进行概率组合的工具了。

coin :: PTable
coin = createPTable ["heads", "tails"] [0.5, 0.5]

spinner :: PTable
spinner = createPTable ["red", "blue", "green"] [0.1, 0.2, 0.7]

ghci> coin <> spinner
heads - red|5.0e-2
heads - blue|0.1
heads - green|0.35
tails - red|5.0e-2
tails - blue|0.1
tails - green|0.35

不仅仅是两个，还可以多个。

ghci> mconcat [coin, coin, coin]
heads - heads - heads|0.125
heads - heads - tails|0.125
heads - tails - heads|0.125
heads - tails - tails|0.125
tails - heads - heads|0.125
tails - heads - tails|0.125
tails - tails - heads|0.125
tails - tails - tails|0.125

ghci> coin <> coin <> coin
heads - heads - heads|0.125
heads - heads - tails|0.125
-- ...

ghci> coin <> coin <> spinner
heads - heads - red|2.5e-2
heads - heads - blue|5.0e-2
heads - heads - green|0.175
heads - tails - red|2.5e-2
heads - tails - blue|5.0e-2
heads - tails - green|0.175
tails - heads - red|2.5e-2
tails - heads - blue|5.0e-2
tails - heads - green|0.175
tails - tails - red|2.5e-2
tails - tails - blue|5.0e-2
tails - tails - green|0.175

一开始可能会觉得幺半群之类的概念很抽象（实际上也确实抽象），但还是可以发现这种抽象的强大力量。

参数化类型

这个概念和泛型很像。最简单的参数化类型是 Box，它类似一个容器，可以将不同类型的值放到这个盒子（Box）里。

data Box a = Box a deriving (Show)

ghci> n = 6 :: Int
ghci> :t Box n
Box n :: Box Int
ghci> f x = x
ghci> :t Box f
Box f :: Box (p -> p)

Rust 语言就提供了类似的类型 Box<T>，当然两者的出发点是不同的，Rust 可能更多是从智能指针的角度出发。而对于 Haskell，我们主要关心的是代数类型。

可以实现一个 wrap 和 unwrap，也可以理解成所谓的装箱和拆箱：

wrap :: a -> Box a
wrap x = Box x

unwrap :: Box a -> a
unwrap (Box x) = x

更有用的可能是 Triple：

data Triple a = Triple a a a deriving (Show)

这个和3-元组（3-tuple）不同，元组是允许不同类型的值组合的，而 Triple 必须是相同的类型。

type Point3D = Triple Double

aPoint :: Point3D
aPoint = Triple 0.1 53.2 12.3

在这个基础上可以提供需要的方法，比如取值：

first :: Triple a -> a
first (Triple x _ _) = x

second :: Triple a -> a
second (Triple _ x _) = x

third :: Triple a -> a
third (Triple _ _ x) = x

再通用的类型就是 List 了。在 ghci 中输入 :info [] 可以看到它的定义：

ghci> :info []
type [] :: * -> *
data [] a = [] | a : [a]

: 是一个数据构造器。这属于 lists 内置的语法，不能直接使用。如果自己定义，是这样的：

data List a = Empty | Cons a (List a) deriving (Show)

在这个定义里，List 是递归的。可以这样读这个定义：

类型 a 的列表 List 要么是空的 Empty，要么连接 a 和另外一个 a 类型的 List。

多个参数的类型

就像函数那样，类型也可以是多个参数。这也意味着这个容器可以包含超过一种类型。

常见的就是元组 Tuples，像列表一样，元组可以有内建的构造器 ()。可以用 ghci 输入 :info (,) 查看类型：

ghci> :info (,)
type (,) :: * -> * -> *
data (,) a b = (,) a b

元组在其它语言中，比如 Python、JavaScript 也都有类似的实现。

另一个有用的多类型参数的类型就是 Map，其它语言中也有叫做字典的，提供键值对的映射。

ghci> import Data.Map
ghci> :info fromList
fromList :: Ord k => [(k, a)] -> Map k a

可以通过两个列表进行 zip 形成元组列表，再通过 fromList 生成 Map：

import qualified Data.Map as Map

data Organ = Heart | Brain | Kidney | Spleen deriving (Show, Eq)

organs :: [Organ]
organs = [Heart, Heart, Brain, Spleen, Spleen, Kidney]

ids :: [Int]
ids = [2, 7, 13, 14, 21, 24]

organPairs :: [(Int, Organ)]
organPairs = zip ids organs

organCatalog :: Map.Map Int Organ
organCatalog = Map.fromList organPairs

ghci> organPairs
[(2,Heart),(7,Heart),(13,Brain),(14,Spleen),(21,Spleen),(24,Kidney)]
ghci> organCatalog
fromList [(2,Heart),(7,Heart),(13,Brain),(14,Spleen),(21,Spleen),(24,Kidney)]
ghci> Map.lookup 7 organCatalog
Just Heart

注意，这里返回的 Just 是 Maybe 的返回类型：

ghci> :info Map.lookup
Map.lookup :: Ord k => k -> Map k a -> Maybe a

Maybe

data Maybe a = Nothing | Just a

在很多语言中，如果找不到，回返回错误，或者得到一个 null 值。但这两种方式会一些问题：

1. 如果采取抛出异常的方式，但很多语言并不要求捕获所有错误。那么可能就因为没有处理这个异常而导致整个程序的崩溃。除此之外，将异常的处理可能是在上层调用中，可能没有足够的信息去处理丢失的情况。
2. 返回 null 问题就更多了，如果程序员一旦没有检查 null，就是致命的问题。然而，也没办法强制程序员检查。

而使用 Maybe 可以以更加聪明的方式来处理这个问题。函数返回 Maybe，那么程序无法直接使用值，而需要处理这个 Maybe。同样有了 Maybe 你也不可能忘记这个值是不是 null。

Maybe 的典型场景：

• 打开文件，文件可能不存在
• 读取数据库数据，数据可能为 null
• RESTful API 可能请求缺失的资源

possibleDrawers :: [Int]
possibleDrawers = [1 .. 50]

getDrawerContents :: [Int] -> Map.Map Int Organ -> [Maybe Organ]
getDrawerContents ids catalog = map getContents ids
  where
    getContents = \id -> Map.lookup id catalog

availableOrgans :: [Maybe Organ]
availableOrgans = getDrawerContents possibleDrawers organCatalog

countOrgan :: Organ -> [Maybe Organ] -> Int
countOrgan organ available = length (filter (\x -> x == Just organ) available)

ghci> countOrgan Brain availableOrgans
1
ghci> countOrgan Heart availableOrgans
2

getDrawerContents 函数返回一个 [Maybe Organ] 列表，其中每个元素都明确表示了存在(Just Organ)或不存在(Nothing)的器官。这比返回 null 或抛出异常要更明确和安全。countOrgan 函数使用 filter 和模式匹配来统计给定器官出现的次数，而不需要做 null 检查，代码更加简洁。