「Learn Haskell」#0 总章

学习一门新语言之Haskell

前言

之前一直很好奇函数式编程，觉得Haskell挺有意思的，想学学
现在高考完放假了，可以有时间具体学一学了
这里没有Haskell的教程，只有我在学习Haskell时写下的笔记

目录

#0 | 总章        
#1 | 基础语法与函数   
#2 | 高阶函数与模块   
#3 | 类型与类型类    
#4 | 输入输出与文件   
#5 | 函子、应用函子与单子
#6 | 半群与幺半群    
#7 | 一些其它类型类   
#A | Haskell与范畴论   

基础运算

• + - * / ()：加减乘除
• div：整除
• mod：取模
• True False：布尔值
• || && not：或且非
• ==：条件判断，相等
• /=：条件判断，不等

函数调用

Haskell中调用函数不加括号，先写出函数名，然后逐个列出参数，用空格隔开：

ghci> max 1 2
2

前缀（prefix）函数与中缀（infix）函数转换：

• 对前缀函数加``使其变成中缀函数
• 对中缀函数加()使其变成前缀函数

ghci> 4 `div` 2
2
ghci> 1 `max` 2
2
ghci> (+) 1 2
3
ghci> (||) True False
True

List

列表是Haskell中很常见的数据类型，和Python中不同，Haskell中的列表中的所有元素必须是同一个类型。

以下是列表常用的函数：

• (++) :: [a] -> [a] -> [a]：合并两个列表
• (:) :: a -> [a] -> [a]：将单个元素并入列表。[1, 2, 3]是1:2:3:[]的语法糖
• (!!) :: [a] -> Int -> a：通过索引取出某个位置上的元素。a !! 1相当于Python中的a[1]
• head :: [a] -> a：返回列表的第一个元素
• tail :: [a] -> [a]：返回列表中除去第一个元素后的列表（若只有一个元素则返回空列表[]）
• last :: [a] -> a：返回列表中的最后一个元素
• init :: [a] -> [a]：返回列表中除去最后一个元素后的列表
• length :: Foldable t => t a -> Int：返回列表的长度
• null :: Foldable t => t a -> Bool：返回列表是否为空
• reverse :: [a] -> [a]：返回翻转后的列表
• take :: Int -> [a] -> [a]：返回列表a的前n个元素的列表(take n a)
• drop :: Int -> [a] -> [a]：返回列表a中除去前n个元素后的列表(drop n a)
• maximum :: (Foldable t, Ord a) => t a -> a：返回列表中的最大值
• minimum :: (Foldable t, Ord a) => t a -> a：返回列表中的最小值
• sum :: (Foldable t, Num a) => t a -> a：返回列表中所有元素的和
• product :: (Foldable t, Num a) => t a -> a：返回列表中所有元素的积
• elem :: (Foldable t, Eq a) => t a -> Bool：判断值n是否在列表a中(

  elem n a
  -- 或
  n `elem` a --用``包上可以变成中缀函数使用

Texas ranges

使用..可以表示出范围并自动推导：

ghci> [1 .. 10]  
[1,2,3,4,5,6,7,8,9,10]  
ghci> ['a' .. 'z']  
"abcdefghijklmnopqrstuvwxyz"  
ghci> ['K' .. 'Z']  
"KLMNOPQRSTUVWXYZ" 
ghci> [2, 4 .. 20]  
[2,4,6,8,10,12,14,16,18,20]  
ghci> [3, 6 .. 20]  
[3,6,9,12,15,18]
ghci> [5, 4 .. 1]
[5,4,3,2,1]

也可以用来生成无穷列表，如[1..]、[1, 3..]。同时也有函数可以生成无穷列表：

• cycle :: [a] -> [a]：将原列表不断循环生成无穷列表
• repeat :: a -> [a]：将传入的值不断重复生成无穷列表
  • replicate :: Int -> a -> [a]：将值a重复n次，返回生成的列表(replicate n a)

List comprehension

Haskell中也有列表推导，形式是一个中括号，左侧为表达式，右侧为变量的范围和约束条件

ghci> [x * 2 | x <- [1 .. 10]]  
[2,4,6,8,10,12,14,16,18,20]  
ghci> [x * 2 | x <- [1 .. 10], x * 2 >= 12]  
[12,14,16,18,20]
ghci> [ x | x <- [50 .. 100], x `mod` 7 == 3]  
[52,59,66,73,80,87,94]   
ghci> [x * y | x <- [2, 5, 10], y <- [8, 10, 11]]  
[16,20,22,40,50,55,80,100,110]

Tuple

Haskell中的元组可以有不同长度，元素可以有不同类型。并且一个元组的类型由其中所有元素的类型共同决定。它的常用函数：

• fst :: (a, b) -> a：返回含有两个元素元组中的第一个元素
• snd :: (a, b) -> b：返回含有两个元素元组中的第二个元素
• zip :: [a] -> [b] -> [(a, b)]：接收两个列表，返回一个列表，每个元素是依次将两个列表中元素配对成的二元组

Syntax in Functions

函数可以直接定义：

plus x y = x + y

这时Haskell会自动推断函数的类型为(Num a) => a -> a -> a。但是最好在定义函数前声明函数的类型：

plus :: (Num a) => a -> a -> a
plus x y = x + y

Pattern matching

定义函数时可以使用模式匹配语法。运行时依次将输入与给出的模式相匹配，如果匹配，就执行对应操作；不匹配，就继续与下一个模式相匹配，直到匹配成功，也因此，最后必须要给出一种通用的匹配来接收与给出模式全不匹配的输入。如：

factorial :: (Integral a) => a -> a  
factorial 0 = 1  
factorial n = n * factorial (n - 1)  

first :: (a, b, c) -> a  
first (x, _, _) = x  
  
second :: (a, b, c) -> b  
second (_, y, _) = y  
  
third :: (a, b, c) -> c  
third (_, _, z) = z  

其中_表示任何值，且不关心它的内容，只是用来占位

列表的(:)操作也可以用来进行模式匹配：

head' :: [a] -> a  
head' [] = error "Can't call head on an empty list, dummy!"  
head' (x:_) = x

sum' :: (Num a) => [a] -> a  
sum' [] = 0  
sum' (x:xs) = x + sum' xs  

但(++)操作不可以用来模式匹配

在针对列表进行模式匹配时，如果同时需要整个列表、列表的第一个值、列表除第一个值外的内容，可以使用xs@(q:qs)。比如[1, 2, 3]通过xs@(q:qs)匹配后，xs为[1, 2, 3]，q为1，qs为[2, 3]

Guard syntax

在函数的定义中，也可以使用守卫（guard）语法：

max' :: (Ord a) => a -> a -> a  
max' a b   
    | a > b     = a  
    | otherwise = b 

先给出传入的参数变量，然后下一行缩进后加|，|后面等号前表示进行的判断，如果为True则返回这个等号后面的值；如果为False则继续判断下一行，直到otherwise

Case expressions

在函数的定义中，也可以使用case表达式来配合模式匹配使用：

case expression of pattern -> result  
                   pattern -> result
                   ...  

例如：

head' :: [a] -> a  
head' [] = error "No head for empty lists!"  
head' (x:_) = x  
-- 等价于：
head' :: [a] -> a  
head' xs = case xs of [] -> error "No head for empty lists!"  
                      (x:_) -> x  

describeList :: [a] -> String  
describeList xs = "The list is " ++ case xs of [] -> "empty."  
                                               [x] -> "a singleton list."   
                                               xs -> "a longer list."  
-- 等价于：
describeList :: [a] -> String  
describeList xs = "The list is " ++ what xs  
    where what [] = "empty."  
          what [x] = "a singleton list."  
          what xs = "a longer list." 

where

声明在函数定义中要使用的局部变量，可以使用where关键字：

initials :: String -> String -> String  
initials firstname lastname = [f] ++ ". " ++ [l] ++ "."  
    where (f:_) = firstname  
          (l:_) = lastname  

在where中，也可以使用上面的模式匹配

let

let <bindings> in <expression>语法可以在函数的定义中使用，也可以在普通算式或列表中使用：

cylinder :: (RealFloat a) => a -> a -> a  
cylinder r h = 
    let sideArea = 2 * pi * r * h  
        topArea = pi * r ^2  
    in  sideArea + 2 * topArea  

ghci> 4 * (let a = 9 in a + 1) + 2  
42 
ghci> [let square x = x * x in (square 5, square 3, square 2)]  
[(25,9,4)] 

if statement

Haskell中的if语句为：

if ... then ...
else ...
-- or if ... then ... else ...
-- or
if ... then ...
else if ... then ...
else ...

其中最后一个else无论如何也不可以省去

Higher Order Functions

Currying

Haskell中的函数是柯里化（Currying）的，可以看作所有函数都只接收一个参数，而接收两个参数的函数实际上是这个函数接收了第一个参数后返回了一个接收第二个参数的函数，然后用这个函数接收第二个参数，返回最终的结果。比如max函数，它的类型签名是：

max :: Ord a => a -> a -> a

可以看成a -> (a -> a)，即接收一个参数，返回一个类型为a -> a的函数。比如max 1的类型签名是：

max 1 :: (Ord a, Num a) => a -> a

因此max 1 2，也就等同于(max 1) 2，即将函数max 1应用在数字2上

同时，函数也可以接收函数作为参数，参数有函数的函数就被称为高阶函数（Higher Order Functions）

一些高阶函数

zipWith

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

第一个参数为一个函数，然后接收两个列表，将其对应元素传入接收的函数中，得到的结果组成一个新的列表。如果两个传入的列表长度不同，以最短的列表为准，长列表中超出的元素省略。用例：

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

flip

flip :: (a -> b -> c) -> b -> a -> c

flip函数接收一个二元函数，返回一个新的二元函数，将其输入的两个参数顺序反过来：

ghci> zip [1,2,3,4,5] "hello"
[(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')]
ghci> flip zip [1,2,3,4,5] "hello"  
[('h',1),('e',2),('l',3),('l',4),('o',5)]

map

map :: (a -> b) -> [a] -> [b]

map函数接收一个函数f和一个列表a，将函数f应用在列表a的每个元素中，并返回得到的所有结果组成的列表b：

ghci> map (+3) [1,5,3,1,6]  
[4,8,6,4,9]  

filter

filter :: (a -> Bool) -> [a] -> [a]

filter函数接收一个函数f和一个列表a，将列表a中的每个元素传入函数f中，如果结果为True就保留，结果为False就抛弃，返回所有保留的元素组成的新列表：

ghci> filter even [1..10]  
[2,4,6,8,10] 

takeWhile

takeWhile :: (a -> Bool) -> [a] -> [a]

takeWhile函数接收一个函数f和一个列表a，将列表a中从左向右每个元素传入函数f，直到结果为False停止，返回停止前传入的所有元素组成的新列表：

ghci> takeWhile (/=' ') "word1 word2"
"word1"

Function application

函数应用可以使用$，$是一个函数，它的类型是：

($) :: (a -> b) -> a -> b

它可以改变函数结合优先级，将左侧函数应用于全部右侧内容上，相当于给右侧整体加上了括号。否则函数默认左结合，会依次向右应用而不会应用在整体上。

f $ g x
-- 等价于
f (g x)
-----
f g x
-- 等价于
(f g) x

Function Composition

函数复合可以使用.，.也是一个函数，它的类型是：

(.) :: (b -> c) -> (a -> b) -> a -> c

定义是：

f . g = \x -> f (g x)

但是函数复合的优先级要比函数执行低，比如：

sum . replicate 5 . max 6.7 8.9

会先执行max 6.7 8.9并返回8.9，然后将sum、replicate 5、8.9复合，但两个函数无法和一个值(8.9)复合，所以会抛出异常。因此要使用$来规定先复合再执行：

sum . replicate 5 . max 6.7 $ 8.9

lambda

Haskell语言中的lambda表达式是用\来表示的（因为看着像$\mathtt{\lambda}$？）
具体语法是

\para1 para2 ... -> return

“->”前的 para1 para2 … 是传入参数，单个多个都可以，需要用空格隔开；”->”后的 return 是计算得到的返回值。一般需要用括号将整个表达式括起来，防止返回值部分一直向右延伸。

fold和scan

fold和scan都接收三个参数（一个二元函数，一个初始值accumulator，一个要折叠的列表），fold返回一个值，而scan返回一个列表
传入的二元函数f :: a -> b -> b将accumulator和从列表中取出的值一同传入（l则accumulator在左边为第一个参数，r则accumulator在右边为第二个参数）

foldl

左折叠，每次从列表最左侧取出一个值，和accumulator一起传入二元函数，并且accumulator在左边为第一个参数，如：

foldl f a xs

它的结果计算过程为

> foldl f a [x1, x2, x3]
[1.] a = f a x1
[2.] a = f a x2 = f (f a x1) x2
[3.] a = f a x3 = f (f (f a x1) x2) x3

可以看出 f (f a x1) x2 其实就是 foldl f a [x1, x2]
而且因此，foldl在计算时最外层需要找到x3，这样如果xs是一个无穷列表，那么将无法计算，陷入无穷。所以foldl虽然看起来从左边取值，但是函数需要从右侧展开，并不适用于无穷列表

foldr

右折叠，每次从列表最右侧取出一个值，和accumulator一起传入二元函数，并且accumulator在右边为第二个参数，如：

foldr f a xs

它的结果计算过程为

> foldr f a [x1, x2, x3]
[1.] a = f x3 a
[2.] a = f x2 a = f x2 (f x3 a)
[3.] a = f x1 a = f x1 (f x2 (f x3 a))

从中可以看出 f x2 (f x3 a) 就是 foldr f a [x2, x3]
因此可以使用递归来写一个和foldr效果一样的函数:

foldr' :: (a -> b -> b) -> b -> [a] -> b
foldr' _ x [] = x
foldr' f a (x:xs) = f x (foldr' f a xs)

也可以看出，最外层计算时只需要x1并且向下递归，并不会接触到列表末尾，因此可以用于无穷列表。foldr即使看上去从右边取值，但是要从左开始展开，可以用于无穷列表

例如：

ghci> foldr (||) False (repeat True)
True    -- 由于逻辑运算存在短路，计算值全应为True，所以直接返回了
ghci> foldl (||) False (repeat True)
-- 这里什么都不会发生，直到电脑内存被爆掉
-- 因为函数刚开始就需要列表最右侧的值，所以在不断计算这个无穷列表

scanl和scanr

scan类似fold，只是将中间得到的每一个值都添加进一个列表中并返回这个列表
scanl则向右延伸这个列表，scanr则向左延伸这个列表
但是它和fold恰恰相反，scanl能用于无穷列表，而scanr不能

> scanr f a [x1, x2, x3]
[1.] 最右侧元素(-1 in python) : a
[2.] 右侧第二个元素(-2) : f x3 a
[3.] 右侧第三个元素(-3) : f x2 (f x3 a)
[4.] 右侧第四个元素(-4) : f x1 (f x2 (f x3 a))

可以看出 f x2 (f x3 a) 是 foldr f a [x2, x3]，也是 scanr f a [x2, x3] 的第一个元素
因此可以用递归来写一个和scanr效果一样的函数：

scanr' :: (a -> b -> b) -> b -> [a] -> [b]
scanr' _ x [] = [x]
-- scanr' f a (x:xs) = f x (foldr f a xs) : scanr' f a xs
scanr' f a (x:xs) = f x q : qs
                    where qs@(q:_) = scanr' f a xs

scanl也是同理：

scanl' :: (b -> a -> b) -> b -> [a] -> [b]
scanl' _ x [] = [x]
scanl' f a (x:xs) = a : scanl' f (f a x) xs

也可以看出，scanr返回的列表的第一个元素是最后添加进去的，所以它无法用于无穷列表。而scanl返回的列表中的元素是从左到右依次添加，可以用于无穷列表截取前一部分结果：

ghci> take 10 (scanl (+) 0 [1..])
[0,1,3,6,10,15,21,28,36,45]
ghci> take 10 (scanr (+) 0 [1..])
[*** Exception: stack overflow

使用foldr编写foldl

pdcxs还给我介绍了一个神奇的操作，用foldl来定义foldr：

foldl' f z xs = foldr (\x g y -> g (f y x)) id xs z

它利用 foldr (\x g y -> g (f y x)) id xs 生成一个函数，作用于z得到结果。

先来看一下foldr的类型：

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
-- 可以看成 (a -> b -> b) -> b -> [a] -> b

但是在这个例子中，类型b并不是一个数字，而是一个函数(b -> b)。

所以这里foldr的类型可以写成：

(a -> (b -> b) -> (b -> b)) -> (b -> b) -> [a] -> (b -> b)

对应于用法 foldr (\x g y -> g (f y x)) id xs ，它返回的值应该是一个函数，类型为 b -> b（后面要作用于z）
而xs对应于[a]；id对应于(b -> b)
所以 (\x g y -> g (f y x)) 要对应于：

(a -> (b -> b) -> (b -> b))

因此可以推断出x的类型是a；y的类型是b；而返回的值为一个类型为(b -> b)的函数。

再看，返回的值是 g (f y x) ，其中 f y x 返回的是一个值，类型为b
所以g接收一个类型b，返回一个类型b -> b。即g的类型为：

b -> (b -> b)

现在根据foldr的定义：

foldr f a (x:xs) = f x (foldr f a xs)

带入计算一下：

xs即为[x1..xn]，为了方便，用xs’来表示[x2..xn]，用xs’’来表示[x3..xn]

定义中的f即为(\x g y -> g (f y x))，a即为id

  foldr (\x g y -> g (f y x)) id xs z
= (\x g y -> g (f y x)) x1 (foldr (...) id xs') z

写完第一步，可以发现，x1 (foldr (…) id xs’) z 正好分别对应了lambda表达式中的x、g、y。可以将其应用，进一步展开：

  (\x g y -> g (f y x)) x1 (foldr (...) id xs') z
= (foldr (...) id xs') (f z x1)

不难发现，原式 (foldr (…) id xs) z 等价于：

(foldr (...) id xs') (f z x1)

跟着这个思路，xs每次少一个开头的元素x’，z每次变换成为 f z x’
因此下一步：

  (\x g y -> g (f y x)) x1 (foldr (...) id xs') z
= (foldr (...) id xs') (f z x1)
= (foldr (...) id xs'') (f (f z x1) x2)
= (foldr (...) id xs''') (f (f (f z x1) x2) x3)
= ...

可以发现，已经有了规律。那么最终停止时是什么样呢？

最后到了不能在展开时，最前面的 foldr (…) id xs 已经变成了 foldr (…) id []
而根据前面foldr的定义 foldr _ x [] = x ，它应该返回id

所以最后的结果：
(id的定义：id x = x)

  ...
= (foldr (...) id xs') (f z x1)
= (foldr (...) id xs'') (f (f z x1) x2)
= ...
= (foldr (...) id []) (f (.. (f z x1) ..) xn)
= id (f (.. (f z x1) ..) xn)
= f (.. (f z x1) ..) xn

那么最后这个结果就很熟悉了，它就是 foldl f z xs。
所以我们推导出了这个用foldr表示foldl的写法是正确的。

Modules

Haskell会自动加载Prelude模块（module），如果在GHCi中再加载其他模块，需要使用:m + ...，比如加载Data.List模块：

Prelude> :m + Data.List

而在hs文件中引入模块，需要使用import语句，下面和python的对比可以便于理解：

import Data.List
-- from Data.List import *

import Data.List (nub, sort)
-- from Data.List import nub, sort

import Data.List hiding (nub)
-- 从Data.List中引入所有，但不引入nub函数

import qualified Data.List
-- import Data.List

import qualified Data.List as Li
-- import Data.List as Li

编写Modules

模块中要包含将要使用的一些函数，像正常的hs文件一样写即可，但头部需要有导出语句（export）。比如一个模块文件名叫ModuleA.hs，那它的头部需要写：

module ModuleA
( functionA
, functionB
, functionC
) where

而且文件中的所有函数只导出需要使用的即可。比如该文件中还含有functionD供前三个函数内部使用，那么在import ModuleA之后也无法调用functionD。

Types & Typeclasses

Types

Haskell有一个静态类型系统，任何变量、函数都会具有类型，并且有类型判断功能，没给出的类型会自动识别。
Type的首字母全为大写，常用的有：

• Int：整型，有上下界范围，-2147483647～2147483648
• Integer：整数，无界，但是效率比Int低
• Float：单精度浮点型
• Double：双精度浮点型
• Bool：布尔值
• Char：字符
• String：字符串，等同于[Char]
• Ordering：大小关系，包含LT、EQ、GT，且它们有大小关系 LT < EQ < GT

列表的类型是由其中元素决定的，并且列表中元素必须是同一类型，所以列表的类型就是其元素类型外加[]。

元组的类型由其中各个元素的类型共同决定，因为元组中的元素可以是不同类型。如(“abc”, ‘a’, True)的类型是([Char], Char, Bool)。

Typeclasses

类型类（Typeclass）是定义一系列功能的接口，如果一个Type属于一个Typeclass的成员，那么它可以实现这个类型类所规定的功能。一个Type也可以属于多个Typeclass
Typeclass的首字母也全为大写，常见的有：

• Eq：可判断是否相等
• Ord：可比较大小
• Show：可展示成字符串
• Read：可从字符串转换成特定类型
• Enum：可枚举（连续），即可以使用pred和succ函数得到前驱和后缀
• Bounded: 有上下界，如果元组中所有元素都属于Bounded，那这个元组的类型也属于Bounded
• Integral：是整数，包括Int和Integer
• RealFloat： 是实浮点数，包括Float和Double
• RealFrac：是实分数，包括Float、Double和Ratio（在Data.Ratio模块中）
• Floating：是浮点数，包括Float、Double和Complex（在Data.Complex模块中）
• Real：是实数，包括Integral和RealFrac的成员
• Fractional：是分数，包括RealFrac和Floating的成员
• Num：是数字，包括上述所有数字相关的类型

Type variables

如果查看一个函数的类型，比如head，那么将会返回以下类型：

head :: [a] -> a

其中的a就是一个类型变量（type variable），它在head中可以属于任何类型，在这里只是表示返回值的类型和输入的列表中的元素的类型相一致。

在函数的类型表达式其实可以看作$\lambda$表达式，它适用于$\alpha$变换（$\alpha$-conversion）。即a在这里可以指Int、Char等类型，也可以指[Char], (Int, Char), 甚至函数Int -> Int等。

在大部分函数的类型中，类型变量需要保证是某个Typeclass的成员才能完成操作。比如(==)函数，它需要传入的参数是可判断相等的，即是Eq的成员，那么(==)的类型就是：

(==) :: (Eq a) => a -> a -> Bool

其中=>前的部分(Eq a)就是类约束（class constraint），它规定了a是Eq的成员，所以(==)函数传入的两个参数都是a类型，且都是Eq的成员，保证了它们之间是可以比较是否相等的。

定义新Type

定义一个新的Type需要使用data关键字，比如定义Bool需要使用：

data Bool = False | True

其中=左侧的部分定义了新类型的名称Bool，右侧的部分叫做值构造器（value constructors），表示了Bool类型的值为False或True。
并且名称和值构造器的首字母都需要大写。

另外，值构造器也是函数，它们可以有参数，叫做项（field）。比如：

data Shape = Circle Float Float Float | Rectangle Float Float Float Float   

它定义了一个新Type叫Shape，值构造器是Circle和Rectangle，Circle接收三个参数都是Float类型，Rectangle接收四个Float类型参数。
如果查看Circle的类型，将返回：

Circle :: Float -> Float -> Float -> Shape

如果想要让它能给直接显示出来，需要让它属于Show类型类。在代码中只需要在结尾加上deriving (Show):

data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)

类型的名称和值构造器名称也可以相同，比如：

data Point = Point Float Float deriving (Show)

导出Type

在文件中定义了新的Type之后，如果在别的文件中将其作为模块导入，则需要先导出。比如文件Shapes.hs中定义了Shape和Point，以及其他的一些函数，那么文件开头需要写：

module Shapes
( Shape(..)
, Point(..)
, functionA
, functionB
) where

其中的Shape(..)导出了Shape类型和它所有的值构造器，..代表了它的所有值构造器。因此，Shape(..)相当于Shape (Circle, Rectangle)。

如果不想要导出值构造器，即不允许使用值构造器的方法来创建Shape类型的变量。那么需要将Shape(..)替换为Shape，这样就只导出了Shape类型，而不导出其值构造器。

Record Syntax

如果想要方便地取出类型实例中的参数，可以使用Record语法，如：

data Point = Point { xcoord :: Float
                   , ycoord :: Float
                   } deriving (Show)

在值构造器的参数部分先加一个大括号，然后指定取出值的函数名称（xcoord, ycoord），后面指定类型（:: Float）。这样xcoord和ycoord就都是一个类型为Point -> Float的函数，可以通过下面方法来访问值：

ghci> let point = Point 1.0 2.0
ghci> xcoord point
1.0
ghci> ycoord point
2.0

同时也可以通过下面方法来创建这个point：

point = Point {ycoord=2.0, xcoord=1.0}

Type parameters

值构造器可以接收参数，类型也可以接收参数，这样它就成为了类型构造器（type constructors）。如Maybe的定义：

data Maybe a = Nothing | Just a

它的值是Nothing时，类型为Maybe a，是多态的（polymorphic）。
他的值不是Nothing时，类型取决于值Just a中a的类型，可以构造出Maybe Int、Maybe [Char]等多种类型：

Nothing :: Maybe a
Just 1 :: Num a => Maybe a
Just 'a' :: Maybe Char
Just "abc" :: Maybe [Char]

可以用这种方法改写Point：

data Point x y = Point { xcoord :: x
                       , ycoord :: y
                       } deriving (Show)

但使用类型参数（type parameters）并不是总是方便，比如在声明函数类型的时候不能只使用Point来表示Point类型，而是必须写成Point Float Float。

而且不能在定义类型构造器时添加类约束（class constraint），不然在之后声明函数类型的时候也都需要添加类约束，如：

data (Ord k) => Map k v = ... 
toList :: (Ord k) => Map k a -> [(k, a)]

Either

Either是一个类型构造器，它有两个值构造器，定义是：

data Either a b = Left a | Right b deriving (Eq, Ord, Read, Show)  

如果使用了Left，那它的a的类型就是具体的；如果使用了Right，那它的b的类型就是具体的：

ghci> Right 20  
Right 20  
ghci> Left "w00t"  
Left "w00t"  
ghci> :t Right 'a'  
Right 'a' :: Either a Char  
ghci> :t Left True  
Left True :: Either Bool b  

Either可以看作Maybe的补充，比如Maybe在使用时，出现异常可以返回Nothing，但只是一个Nothing，不包含任何信息；但Either包含左值和右值，正常结果返回右值，而出现异常就可以返回包含错误信息的左值，比如安全除法：

safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)

ghci> safeDiv 4 2
Just 2
ghci> safeDiv 1 0
Nothing

而使用Either：

safeDiv :: Int -> Int -> Either String Int
safeDiv _ 0 = Left "Divided by zero"
safeDiv x y = Right (x `div` y)

ghci> safeDiv 4 2
Right 2
ghci> safeDiv 1 0
Left "Divided by zero"

Derived instances

想要使一个定义的类满足某些Typeclass的需求，需要从其派生（derive），比如：

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday   
           deriving (Eq, Ord, Show, Read, Bounded, Enum)  

这样Day类型的值（Monday～Sunday）之间就可以比较是否相等（从Eq派生），比较大小（从Ord派生，左侧为小，右侧为大），显示成字符串（从Show派生），从字符串中读取（从Read派生），包含边界（从Bounded派生），可以枚举（从Enum派生，按照值构造器中的顺序依次向右）

Type synonyms

为了阅读方便，书写简便，可以使用type关键字为已有类型创建别名（synonyms）。比如String的定义：

type String = [Char]

在所有需要使用字符串（即[Char]）的地方都可以使用String来代替，它们是完全一致的，只是String更简便易读。
同时，类型别名也可以接收类型参数

newtype keyword

除了data、type关键字之外，还可以用newtype关键字来定义一个新的类型，比如Control.Applicative模块中的ZipList：

newtype ZipList a = { getZipList :: [a] }

• 不同于type，它不是别名，可以使用record语法来直接定义取出值的函数
• 不同于data，它只能有一个值构造器，但是速度要比data快，而且更加懒惰

Recursive data structures

一个类型也可以递归定义，比如一颗二叉树：

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)  

定义新Typeclass

定义一个新的Typeclass需要使用class关键字，例如定义Eq类型类：

class Eq a where  
    (==) :: a -> a -> Bool  
    (/=) :: a -> a -> Bool  
    x == y = not (x /= y)  
    x /= y = not (x == y)  

其中a是一个类型变量，前两行声明了需要实现的函数的名字及其类型，后两行表明了需要的函数之间可以相互定义（不必要）。

包含了后两行之后，只定义(==)函数或者(/=)函数都可以完成全部定义，它们（(==) | (/=)）成为这个类型类的最小完整定义（minimal complete definition）

查看一个类型类的成员需要实现的函数可以在GHCi中使用:info：

ghci> :info Eq

手动创建实例

使一个类型成为一个类型类的实例可以直接使用deriving来自动完成，也可以通过使用instance关键字来手动完成。比如使Point成为Show的实例：

instance Show Point where
    show (Point x y) = "(" ++ show x ++ ", " ++ show y ++ ")"

-- in ghci
ghci> Point 1.0 2.0
(1.0, 2.0)

这样就可以自定义显示的内容，否则使用deriving的话只会直接将其转化为字符串。

同时也要注意类型和类型构造器的区别，传入给instance的第二个参数应该为类型而不是类型构造器，比如Maybe：

instance Eq Maybe where  
    ...    
-- 错误用法，因为Maybe是类型构造器而不是类型

instance Eq (Maybe m) where  
    ...
-- 错误用法，因为m不一定是Eq的成员

instance (Eq m) => Eq (Maybe m) where  
    Just x == Just y = x == y  
    Nothing == Nothing = True  
    _ == _ = False  

Functor Typeclass

Functor也是一种类型类，它只规定了一个函数：

class Functor f where
    fmap :: (a -> b) -> f a -> f b

其中f是一个类型构造器，而不是一个具体类型

Kinds

一个值的类型叫做类型（Type），而一个类型的类型叫做Kind。可以通过GHCi中:k来查看Kind：

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

其中的星号*代表了一个具体类型（concrete type）。Int本身就是一个具体类型，所以Int的Kind是*。而Maybe是一个类型构造器，它接收一个具体类型返回一个新的具体类型，所以Maybe的Kind是* -> *。如果给Maybe传入了一个Int，那么得到的Maybe Int就是一个具体的类型，它的Kind就是*。Either也是一个类型构造器，但它接收两个类型才产生一个新的类型，所以Either的Kind是* -> * -> *。

Input/Output

运行Haskell程序

不在GHCi中运行一个Haskell程序有两种方式：

1. 编译运行：

   $ ghc --make code
   $ ./code

2. 通过runhaskell命令直接运行：

   $ runhaskell code.hs

输出文本

在一个Haskell程序中输出文字需要定义一个main函数：

main = putStrLn "Hello World"

其中putStrLn的类型是：

putStrLn :: String -> IO ()

putStrLn接收一个String类型，并返回一个结果为()类型的IO动作（I/O action）。所以main函数的类型为IO ()。（IO的Kind是* -> *）

除此之外，还有其他默认提供的输出文本的函数：

• putStr：输出文本，结尾不换行
• putChar：输出单个字符，结尾不换行。接收的参数为单个Char，不是String（用单引号不是双引号）
• print：可以接收任何Show的成员，先用show转化为字符串然后输出。等同于putStrLn . show

do block

在main函数中使用多个putStrLn需要使用do语句：

main = do
    putStrLn "Line1"
    putStrLn "Line2"

其中最后一行一定要返回IO ()类型的值

输入文本

输入文字需要在do块中使用getLine：

main = do
    line <- getLine
    putStrLn line

getLine的类型是：

getLine :: IO String

而<-操作符将getLine中的String提取了出来给到了line，使line变成了String类型的一个字符串。

而且使用输入的字符串必须要经过一次<-，不能直接使用getLine作为字符串，因为getLine不是String类型，而是IO String类型。

除此之外，还可以使用getChar来获取单个字符，但仍然需要使用<-操作符来提取Char

其他IO相关函数用法

return

Haskell中的return和其他命令式语言中的return完全不同，它不会使函数直接结束并返回一个值。

main函数必须定义为类型为IO ()的函数，所以在main函数中使用if语句，如果不输出的话也不可以直接放下什么都不干，因为这时候main函数的类型不是IO ()。所以这时需要使用return ()来为main函数指定为IO ()类型，例如：

main = do 
    line <- getLine
    if null line
        then return () -- <-这里
        else do
            ...

使用<-操作符也可以直接将return语句中的内容提取出来，比如a <- return ‘A’，执行后a就是’A’。

when

when包含在Control.Monad模块中，它表示在满足第一个参数的条件下会执行第二个函数，否则会return ()。比如：

import Control.Monad   
  
main = do  
    c <- getChar  
    when (c /= ' ') $ do  
        putChar c  
        main  

等同于：

main = do     
    c <- getChar  
    if c /= ' '  
        then do  
            putChar c  
            main  
        else return () 

sequence

sequence在IO中使用时可以达成[IO a] -> IO [a]的效果，所以可以用作：

[a, b, c] <- sequence [getLine, getLine, getLine]

mapM & mapM_

在IO相关的地方使用map，可以使用mapM和mapM_，其中mapM有返回值而mapM_直接扔掉了返回值：

ghci> mapM print [1,2,3]  
1  
2  
3  
[(),(),()]  
ghci> mapM_ print [1,2,3]  
1  
2  
3  

forever

forever函数包含在Control.Monad模块中。在main函数开头加上forever函数可以使后面的do块一直重复执行直到程序被迫终止，如：

import Control.Monad
  
main = forever $ do
    ...

forM

forM函数包含在Control.Monad模块中，它的功能和mapM类似，从第一个参数中逐个取出元素传入第二个参数（一个接收一个参数的函数）中，并且第二个参数可以返回IO a类型。比如：

import Control.Monad

main = do 
    colors <- forM [1, 2, 3, 4] (\a -> do
        putStrLn $ "Which color do you associate with the number " ++ show a ++ "?"  
        color <- getLine  
        return color)
    putStrLn "The colors that you associate with 1, 2, 3 and 4 are: "  
    mapM putStrLn colors

getContents

getLine获取一整行，而getContents从标准输入中获取全部内容直到遇到EOF，并且它是lazy的，在执行了foo <- getContents后，它并不会读取标准输入并且赋值到foo，而是等到需要使用foo的时候再从标准输入读取。

getContents在使用管道传入文字时很常用，可以代替forever+getLine使用，比如一个Haskell程序文件code.hs：

import Data.Char  
  
main = do  
    contents <- getContents  
    putStr (map toUpper contents)  

使用ghc –make code编译后，通过管道传入文字：

cat text.txt | ./code

会将text.txt中的所有字母转为大写并输出

interact

上述功能还可以转化为一个String -> String的函数：

upperStrings = unlines . map (map toUpper) . lines

而在main中使用这个函数就需要：

main = do
    contents <- getContents
    putStr (upperStrings contents)

但是String -> String类型的函数在输入输出中的使用太常见了，所以可以使用interact函数来简化。interact的类型是：

interact :: (String -> String) -> IO ()

可以看出它接收一个String -> String的函数，并返回一个IO ()类型，所以可以直接用在main上。

于是整个转换为大写的程序就可以简化为：

main = interact $ unlines . map (map toUpper) . lines

文件和流

以下与文件和流相关的函数都包含在System.IO模块中

openFile

openFile函数可以用来打开一个文件，它的类型是：

openFile :: FilePath -> IOMode -> IO Handle

其中FilePath是String的type synonyms，用一个字符串来表示需要打开的文件的路径

IOMode的定义是：

data IOMode = ReadMode | WriteMode | AppendMode | ReadWriteMode

所以它一共只有四个值，用来表示进行IO操作的模式

openFile返回一个IO Handle类型的值，将其用<-操作符提取后会出现一个Handle的值。但不能从Handle中直接使用文字，还需要使用一系列函数：

• hGetContents :: Handle -> IO String ，从Handle中读取全部内容，返回一个IO String
• hGetChar :: Handle -> IO Char ，从Handle中读取一个字符
• hGetLine :: Handle -> IO String ，从Handle中读取一行，返回一个IO String
• hPutStr :: Handle -> String -> IO () ，向Handle中输出字符串
• hPutStrLn :: Handle -> String -> IO () ，同上

在使用openFile进行文件操作后，需要使用hClose手动关闭Handle。hClose :: Handle -> IO ()，接收一个Handle并返回IO ()，可以直接放在main函数末尾

所以使用openFile读取一个文件中的全部内容并输出的全部代码是：

import System.IO

main = do
    handle <- openFile "text.txt" ReadMode
    contents <- hGetContents handle
    putStrLn contents
    hClose handle

withFile

withFile类似Python中的with open，它在读取文件使用之后不需要手动close文件。它的类型是：

withFile :: FilePath -> IOMode -> (Handle -> IO a) -> IO a

可以看出，它接收三个参数：

• FilePath：一个表示文件路径的String
• IOMode：打开文件的模式
• (Handle -> IO a)：一个函数，表示对读取文件后的Handle索要进行的操作，需要返回一个I/O action；而这个返回值也将作为withFile的返回值

现在使用withFile来改写上述代码：

import System.IO

main = withFile "text.txt" ReadMode (\handle -> do
    contents <- hGetContents handle
    putStrLn contents)

withFile的功能相当于以下函数：

withFile' :: FilePath -> IOMode -> (Handle -> IO a) -> IO a  
withFile' path mode f = do  
    handle <- openFile path mode   
    result <- f handle  
    hClose handle  
    return result  

readFile

readFile可以更加简化读取文件内容的操作，它的类型：

readFile :: FilePath -> IO String

它只需要输入一个表示文件路径的字符串，返回其中以其中内容为内容的I/O action：

import System.IO

main = do
    contents <- readFile "text.txt"
    putStrLn contents

writeFile

writeFile简化了写入文件的操作，它的类型：

writeFile :: FilePath -> String -> IO ()

传入的第一个参数是要写入的文件的路径，第二个参数是要写入的字符串，返回一个IO ()

appendFile

appendFile类似writeFile，但使用它不会覆盖文件中原来内容，而是直接把字符串添加到文件末尾

buffer

文件以流的形式被读取，默认文字文件的缓冲区（buffer）大小是一行，即每次读取一行内容；默认二进制文件的缓冲区大小是以块为单位，如果没有指定则根据系统默认来选择。

也可以通过hSetBuffering函数来手动设置缓冲区大小，这个函数的类型：

hSetBuffering :: Handle -> BufferMode -> IO ()

它接收一个handle，和一个BufferMode，并返回IO ()。其中BufferMode有以下几种：

• NoBuffering：没有缓冲区，一次读入一个字符
• LineBuffering：缓冲区大小是一行，即每次读入一行内容
• BlockBuffering (Maybe Int)：缓冲区大小是一块，块的大小由Maybe Int指定：
  • BlockBuffering (Nothing)：使用系统默认的块大小
  • BlockBuffering (Just 2048)：一块的大小是2048字节，即每次读入2048bytes的内容

缓冲区的刷新是自动的，也可以通过hFlush来手动刷新

hFlush :: Handle -> IO ()

传入一个handle，返回IO ()，即刷新对应handle的缓冲区

openTempFile

openTempFile可以新建一个临时文件：

openTempFile :: FilePath -> String -> IO (FilePath, Handle)

FilePath指临时文件要创建的位置路径，String指临时文件名字的前缀，返回一个I/O action，其内容第一个FilePath是创建得到的临时文件的路径，Handle是临时文件的handle

例如：

import System.IO

main = do
    (tempFile, tempHandle) <- openTempFile "." "temp"
    ...
    hClose tempHandle

"."指临时文件要在当前目录创建，"temp"指临时文件名字以temp开头。最终得到的tempFile就是./temp…….，temp后为随机数字，如./temp43620-0

路径操作

相关函数都包含在System.Directory模块中，全部内容见System.Directory

getCurrentDirectory

getCurrentDirectory :: IO FilePath

直接返回一个I/O action，其内容是一个字符串表示当前路径的绝对路径

removeFile

removeFile :: FilePath -> IO ()

输入一个文件路径，并删除掉它

renameFile

renameFile :: FilePath -> FilePath -> IO ()

输入一个原路径，一个新路径，为原路径的文件重命名为新路径的名

doesFileExist

doesFileExist :: FilePath -> IO Bool

检查文件是否存在，返回一个包含布尔值的I/O action

Command line arguments

System.Environment模块中提供了两个函数可以用来处理传入命令行的参数

getArgs

getArgs :: IO [String]

不需要输入参数，直接返回一个I/O action，内容为传入命令行的参数（一个由String组成的列表）。相当于C语言中的argv[1:]

getProgName

getProgName :: IO String

返回I/O action，内容为程序的名字，相当于C语言中的argv[0]

Randomness

和随机数有关的函数都包含在System.Random模块中。GHCi启动时可能不会包含System.Random的配置，导致无法找到模块。需要通过stack打开:

stack ghci --package random

Haskell要求同样的程序需要运行出同样的结果，除了用到了I/O action，所有会造成不同结果的函数都要交给I/O action来完成

那要使随机数脱离IO存在，就要用到随机生成器（random generator）

System.Random模块提供了几个生成随机数的函数：

random

random :: (Random a, RandomGen g) => g -> (a, g)

其中又有两个新的typeclass，Random表示可以取随机，RandomGen表示随机数生成器。random函数接收一个随机数生成器，返回一个元组，其中第一个元素是生成的随机数，第二个元素是一个新的随机数生成器

获取随机数生成器可以使用mkStdGen函数：

mkStdGen :: Int -> StdGen

其中StdGen是一个RandomGen的实例

运用random生成随机数需要指定类型，不然程序无法确定a是什么类型。例如：

ghci> random (mkStdGen 100) :: (Int, StdGen)
(9216477508314497915,StdGen {unStdGen = SMGen 712633246999323047 2532601429470541125})
ghci> random (mkStdGen 100) :: (Char, StdGen)
('\537310',StdGen {unStdGen = SMGen 712633246999323047 2532601429470541125})
ghci> random (mkStdGen 100) :: (Bool, StdGen)
(True,StdGen {unStdGen = SMGen 712633246999323047 2532601429470541125})

再次运行同样的函数，会得到同样的结果。所以如果需要生成其他的随机数，需要更换生成器，就可以使用上一次调用结果返回的新随机数生成器：

threeCoins :: StdGen -> (Bool, Bool, Bool)  
threeCoins gen =   
    let (firstCoin, newGen) = random gen  
        (secondCoin, newGen') = random newGen  
        (thirdCoin, newGen'') = random newGen'  
    in  (firstCoin, secondCoin, thirdCoin) 

randoms

randoms :: (Random a, RandomGen g) => g -> [a]

randoms接收一个RandomGen，返回一个随机的无穷列表。因为它是无穷的，所以不会返回新的随机数生成器

randomR

randomR :: (Random a, RandomGen g) => (a, a) -> g -> (a, g)

可以用来生成有范围的随机数，第一个参数是一个元组，表示生成随机数的范围(闭区间)

randomRs

randomRs :: (Random a, RandomGen g) => (a, a) -> g -> [a]

同上两个，生成有范围的无穷随机数列表

getStdGen

如果想要让程序每次运行得到不同的随机结果，需要使用getStdGen来获取全局随机数生成器，它会在每次运行的时候产生不同的值，也因此，它返回的是一个I/O action，而不是一个直接的StdGen

getStdGen :: Control.Monad.IO.Class.MonadIO m => m StdGen

即可以看成getStdGen :: IO StdGen，需要使用<-操作符将StdGen提取出来

但是在同一个程序中，getStdGen的结果是相同的，全局随机数生成器不会自动更新，所以就需要另一个函数newStdGen

newStdGen

newStdGen :: Control.Monad.IO.Class.MonadIO m => m StdGen

执行newStdGen会进行两个操作：

• 更新全局随机数生成器，下次执行getStdGen会获得不同的结果
• 返回一个I/O action，包含一个新的StdGen（但是这个生成器和全局生成器也不同）

Exceptions

程序在运行失败时会抛出异常，可以通过Control.Exception模块中的catch函数来捕获异常：

catch :: Exception e => IO a -> (e -> IO a) -> IO a

第一个参数是要进行的操作，以IO a为返回值的类型，第二个参数是一个函数，它接收异常并进行操作，例如：

import Control.Exception

main = main' `catch` handler

main' :: IO ()
main' = do
    ...

handler :: Exception e => e -> IO ()
handler e =  putStrLn "..."

也可以利用守卫（guard）语法和System.IO.Error中的函数来判断IO异常的类型来进行不同操作：

import System.Environment
import System.IO.Error
import Control.Exception
  
main = toTry `catch` handler
              
toTry :: IO ()  
toTry = do (fileName:_) <- getArgs  
           contents <- readFile fileName  
           putStrLn $ "The file has " ++ show (length (lines contents)) ++ " lines!"  
  
handler :: IOError -> IO ()  
handler e  
    | isDoesNotExistError e = putStrLn "The file doesn't exist!"  
    | otherwise = ioError e  

具体相关全部函数见文档：System.IO.Error、Control.Exception

Functors

函子（Functor）是一个类型类（typeclass），和其他类型类一样，它规定了其实例类必须实现的功能（例如Eq类型类规定了它的实例必须是可以比较是否相等的），Functor规定类它的实例必须是可以进行映射的。Functor要求使用fmap :: (a -> b) -> f a -> f b 函数来实现这个功能，它接收一个a -> b类型的函数、一个内部元素为a类型的函子，返回一个内部元素为b类型的函子

Functor可以比作盒子，那fmap函数就相当于给定一个函数和一个盒子，将盒子中的全部元素都应用这个函数，再返回应用函数后的盒子

函子的实例必须是一个Kind为* -> *的类型构造器，因为它要求其是一个盒子，盒子在接收内容后才会成为一个具体的类型。fmap中的f a和f b也是因为f是一个类型构造器，在接收类型a/b后才会变成一个具体类型（f a和f b）出现在函数类型声明中

Functor的定义是:

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$) :: a -> f a -> f b
    (<$) = fmap . const

可以发现Functor不仅需要fmap函数，还需要一个<$函数，它接收一个a类型的变量和一个内容为b类型的函子，返回一个内容为a类型的函子；作用就是将传入的函子中的所有元素都替换为传入的第一个参数，比如：

ghci> 'a' <$ [1, 2, 3]
"aaa"

但它不是声明一个函子实例必须的，因为它可以使用fmap和const函数复合来实现，其中const的类型签名：

const :: a -> b -> a

即接收两个参数，但始终只返回第一个参数

Functor实例

[]

列表[]是一个函子，它通过map函数来实现fmap的功能：

instance Functor [] where
    fmap = map

map :: (a -> b) -> [a] -> [b]

map和fmap要求的相同，达成的目的也一致。map接收一个函数和一个列表，它会将列表中的所有元素都应用这个函数后再返回这个列表

Maybe

Maybe也具有kind * -> *，它也是一个函子：

instance Functor Maybe where
    fmap f Nothing = Nothing
    fmap f (Just x) = Just (f x)

ghci> fmap (*2) Nothing
Nothing
ghci> fmap (*2) (Just 2)
Just 4

Either a

Either的kind是* -> * -> *，显然它不是函子，但是固定了一个传入类型的Either a的kind是* -> *，也是一个函子：

instance Functor (Either a) where
    fmap f (Left x) = Left x
    fmap f (Right x) = Right (f x)

ghci> fmap (*2) (Left 4)
Left 4
ghci> fmap (*2) (Right 4)
Right 8

因为使用Either时一般用右值表示正常结果，左值表示异常信息，所以使用fmap时只对右值进行操作，如果时左值则保持不变（而且左值此时也作为确定类型确定值存在）

IO

IO也是一个函子，使用fmap对IO中内容应用函数：

instance Functor IO where
    fmap f action = do
        result <- action
        return (f result)

ghci> fmap ("input: "++) getLine
test
"input: test"

(,) a

(,)表示一个二元组的类型构造器，(,) :: * -> * -> *，而确定了第一个元素的类型后就变成了(,) a，它的kind是* -> *。也是一个函子，进行fmap函数时只对第二个元素应用：

instance Functor ((,) a) where
    fmap f (x, y) = (x, f y)

只剩一个元素的三元组和四元组也都是函子，fmap也只对最后一个元素应用：

instance Functor ((,,) a b) where
    fmap f (a, b, c) = (a, b, f c)

instance Functor ((,,,) a b c) where
    fmap f (a, b, c, d) = (a, b, c, f d)

(->) r

->也是一个类型构造器，它的kind：

(->) :: * -> * -> *

一个映射（一元函数）的类型a -> b也可以写成(->) a b，它是由类型a和类型b输入到类型构造器->中后形成的一个具体类型。所以确定了输入类型后的一元函数的类型就是(->) r（其中r是输入的类型）

规定的fmap的类型签名是：

fmap :: (a -> b) -> f a -> f b

其中的f是函子，而在这个实例中(->) r就是函子，将其带入f可以得到：

fmap :: (a -> b) -> ((-> r) a) -> ((-> r) b)

把其中的(->)换成中缀可以得到：

fmap :: (a -> b) -> (r -> a) -> (r -> b)

传入两个函数，一个类型为a -> b，一个类型为r -> a，返回一个函数，类型为r -> b。
不难推测这个fmap是将这两个函数复合了，先对输入对r应用第二个函数产生类型a的结果，然后在应用第一个函数产生类型b的结果，所以(->) r定义的fmap是：

instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

所以(->) r的fmap其实就是函数复合(.)：

instance Functor ((->) r) where
    fmap = (.)

ghci> :t fmap (*3) (+100)  
fmap (*3) (+100) :: (Num a) => a -> a  
ghci> fmap (*3) (+100) 1  
303  
ghci> (*3) `fmap` (+100) $ 1  
303  
ghci> (*3) . (+100) $ 1  
303

Functor Laws

所有的函子都应该满足两个定律。这两个定律不是Haskell强制要求的，但应该确保一个函子满足这两个定律：

1. fmap id = id（其中id为函数(\x -> x)）：即对一个函子fmap id，那它应该返回本身（fmap id a = id a = a，a为一个函子），比如：

   ghci> fmap id [1, 2, 3]
   [1,2,3]
   ghci> fmap id (Just 2)
   Just 2

2. fmap (f . g) = fmap f . fmap g：即函子的fmap支持结合律
   fmap (f . g) a = fmap f . fmap g $ a = fmap f (fmap g a)，其中a为一个函子
   fmap (f . g) (Just x) = fmap f (fmap g (Just x)) = fmap f (Just (g x)) = Just (f (g x))

   ghci> fmap ((*3) . (+100)) (Just 1)
   Just 303

满足第一个定律的函子一定满足第二个定律，所以只要检查函子是否满足第一个定律即可

Intuition

对于函子和fmap，有两种理解方法

1. 函子是一种容器（container）；fmap接收一个函数和一个容器，在容器内部应用这个函数，返回应用后的新容器
2. 函子是一种计算上下文（context）；fmap是柯里化的，把其类型签名看作

   fmap :: (a -> b) -> (f a -> f b)

   接收一个函数返回另一个函数，传入函数g :: a -> b，fmap将其转换为新的函数

   fmap g :: f a -> f b

   使普通的函数g可以在计算上下文f中使用，这种转换也被称为提升（lift）

常用函数

<$>

<$>函数是fmap的中缀形式（它看着类似$，f $ 3将f应用在单个值3上，而f <$> [1, 2, 3]将f应用在一个函子上，也就是应用在一个函子内部的所有值上）：

ghci> fmap (*2) (Just 2)
4
ghci> (*2) <$> Just 2
4

$>

$>函数包含在Data.Functor模块中

($>) :: Functor f => f a -> b -> f b

Functor定义时要求了<$函数，将函子内部的元素全部替换为指定的某个值，而$>正好将<$函数的两个参数反了过来，相当于flip (<$)：

ghci> 'a' <$ [1, 2, 3]
"aaa"
ghci> [1, 2, 3] $> 'a'
"aaa"

void

void函数也包含在Data.Functor模块中

void :: Functor f => f a -> f ()

void函数把一个函子内部的全部元素都变成空（()），void x相当于() <$ x：

ghci> void [1, 2, 3]
[(), (), ()]
ghci> void (Just 2)
Just ()

Applicative Functor

应用函子（Applicative Functor）是函子的升级版，它包含在Control.Applicative模块中。

fmap进行的操作是将一个普通一元函数应用在一个函子内部。而如果要将一个包含函数的函子应用在另一个函子上，fmap就处理不了了，但是应用函子的方法可以处理。应用函子的定义：

class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

应用函子要求实现两个函数：

• pure :: a -> f a，不难理解，pure接收一个值，并将其放在默认的上下文/容器中。对于列表，pure = []；对于Maybe，pure = Just
• <*> :: f (a -> b) -> f a -> f b，类似于fmap :: (a -> b) -> f a -> f b，但不同的是<*>的第一个参数的类型是f (a -> b)不是a -> b。所以<*>的第一个参数是在上下文中的函数，而不是一个普通函数。换句话说，<*>接收一个装有函数的函子和另一个函子，应用函数后返回新的函子。

Applicative Functor实例

Maybe

Maybe是一个应用函子：

instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something

• pure函数：将一个值放在默认的上下文中，而对于Maybe，默认的上下文就是Just，所以pure x = Just x
• <*>函数：将装有函数的函子中的函数应用另一个函子中
  • 第一个参数是Nothing，即第一个函子不包含函数，那返回的结果就也会是Nothing
  • 第一个参数是装有函数f的函子Just f，将其中的函数f应用在函子something中，只需要将f提取出来使用fmap应用在函子something中即可

实际应用的例子：

ghci> Just (+3) <*> Just 9
Just 12
ghci> pure (+3) <*> Just 9
Just 12
ghci> (+3) <$> Just 9
Just 12
ghci> Nothing <*> Just 9
Nothing

第一个例子，Just (+3)是一个包含函数(+3)的函子，将其应用在函子Just 9中，将Just (+3)中的函数(+3)提取出来，应用在Just 9中，得到了Just 12

第二个例子，可以发现，在这里pure (+3)和Just (+3)等效，因为pure将函数(+3)放在默认上下文中，也就是Just中了

而<*>能做的不止这些，他可以连续传入更多函子作为参数，比如：

ghci> pure (+) <*> Just 3 <*> Just 9
Just 12
ghci> pure (\x y z -> x + y + z) <*> Just 3 <*> Just 4 <*> Just 5
Just 12

<*>函数一样是默认左结合的，pure (+) <*> Just 3 <*> Just 9相当于(pure (+) <*> Just 3) <*> Just 9，而pure (+) <*> Just 3将(+)应用在Just 3上，得到的就是Just (+3)一个包含函数的函子，又将其通过<*>应用在了Just 9上，得到了Just 12:

  pure (\x y z -> x + y + z) <*> Just 3 <*> Just 4 <*> Just 5
= (pure (\x y z -> x + y + z) <*> Just 3) <*> Just 4 <*> Just 5
= (Just (\y z -> 3 + y + z) <*> Just 4) <*> Just 5
= Just (\z -> 3 + 4 + z) <*> Just 5 = Just (+7) <*> Just 5
= Just 12

所以可以使用类似pure f <*> x <*> y <*> …来将一个普通多元函数f应用在多个函子上。

而且pure f <*> x实际上先将普通函数f放在上下文中，然后执行<*>时再将其提取出来执行fmap，所以它就相当于将普通函数应用在函子x上，即fmap f x，也可以写成f <$> x。所以常用的写法就是：

f <$> x <*> y <*> ...

[]

列表也是一个应用函子：

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

• pure函数：对于列表而言，一个值的最小上下文就是只包含这个值的列表[x]
• <*>函数：列表的<*>函数是通过列表推导来实现的。因为不同于Maybe的Just只包含一个值，列表可以包含很多值，第一个传入的列表中可能会包含很多函数，第二个传入的列表也会包含很多值，所以就需要先从第一个列表中取出一个函数然后依次应用在第二个列表的每个值中，再取出第一个列表中的第二个函数应用在第二个列表的每个值中……最终返回得到的所有结果的列表

使用例子：

ghci> [(+3), (*2)] <*> [1, 2]
[4,5,2,4]
ghci> [(+), (*)]  <*>  [1, 2]  <*>  [3, 4]  
[4, 5, 5, 6, 3, 4, 6, 8]

IO

instance Applicative IO where
    pure = return
    a <*> b = do
        f <- a
        x <- b
        return (f x)

也不难理解，pure函数直接将传入的值return，相当于放在了IO的上下文中。而<*>函数先将两个IO中内容提取出来，然后应用函数后return，形成新的IO函子

ghci> (++) <$> getLine <*> getLine
Line1
Line2
"Line1Line2"

(->) r

(->) r同样也是一个应用函子，和函子的分析一样，先来分析它的<*>函数的类型签名：

<*> :: f (a -> b) -> f a -> f b

其中f为(->) r，将其代入并替换为中缀：

<*> :: (r -> a -> b) -> (r -> a) -> (r -> b)

可以看出它接收两个函数f :: r -> a -> b、g :: r -> a，返回另一个函数h :: (r -> b)

那么返回的函数的输入为r，输出为b，所以先对输入应用函数g得到a，然后在对r和a应用f得到b，所以推测<*>函数的操作就是：

\x -> f x (g x)

于是：

instance Applicative ((->) r) where
    pure x = (\_ -> x)
    f <*> g = \x -> f x (g x)

将一个值放在函数的上下文中，最小上下文就应该返回这个值本身，所以pure函数定义为(_ -> x)，即无论输入什么，都返回x

应用函子的<*>函数接收两个函子，返回一个新的函子。对于(->) r，它接收两个函数，返回一个新的函数。具体例子：

ghci> (+) <$> (+3) <*> (*100) $ 5
508

执行这句时发生了什么？：

  (+) <$> (+3) <*> (*100) $ 5
= ((+) <$> (+3)) <*> (*100) $ 5
= ((+) . (+3)) <*> (*100) $ 5 = (\a -> (+) ((+3) a)) <*> (*100) $ 5
= (\a b -> (a + 3 + b)) <*> (*100) $ 5
= (\x -> x + 3 + ((*100) x)) $ 5
= (\x -> x + 3 + x * 100) $ 5
= 5 + 3 + 5 * 100 = 508
= (5 + 3) + (5 * 100)

所以就相当于先对输入分别执行(+3)和(*100)，然后将两个结果执行了(+)

同样：

ghci> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5  
[8.0,10.0,2.5]  

先对5分别执行(+3)、(*2)、(/2)，然后将得到的三个结果传入(\x y z -> [x,y,z])得到了最终的结果

  f <$> g <*> h <*> i
= (\x -> f (g x) (h x) (i x))

ZipList

普通列表实现的<*>函数是将每个函数应用在所有值上，但还有一种实现方法是将每个函数应用在对应值上，因为同一个类型不能存在同一函数的两种实现形式，所以引入了一个新的列表ZipList，包含在Control.Applicative模块中

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

但是ZipList并不是Show的实例，所以不能直接显示出来，要使用getZipList来获取它内部的列表：

ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100..]  
[101,102,103]
ghci> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "cat" <*> ZipList "rat"  
[('d','c','r'),('o','a','a'),('g','t','t')]  

Applicative Functor Laws

应用函子一般有四个定律，都是保证pure的正确性的：

1. Identity law：pure id <*> v = v
2. Homomorphism：pure f <*> pure x = pure (f x)
3. Interchange：u <*> pure v = pure ($ v) <*> u
4. Composition：u <*> (v <*> w) = pure (.) <*> u <*> v <*> w

Intuition

理解应用函子的方式也是将其看作是计算上下文（context），比如要计算：
$$
[[\ \ g\ x_1\ x_2\ \cdots\ x_n\ \ ]]
$$

其中$x_i$的类型是$f\ t_i$，$f$是应用函子（看作上下文）。而函数$g$的类型是：

$$
t_1\to t_2\to\cdots\to t_n\to t
$$

所以双括号（idiom brackets）的作用是将一个普通函数应用在包含在上下文中的参数上。$g\ x_1$可以通过fmap来执行，将$g$提升（lift）到$x_1$的上下文中，然后应用在$x_1$上。但是fmap返回的结果是一个函子，换句话说，$g\ x_1$结果的类型是：

$$
f\ \ (t_2\to t_3\to\cdots\to t_n\to t)
$$

但是fmap并不能将上下文中的函数应用在上下文中的参数上，于是应用函子的<*>函数提供了这个方法，所以计算$[[\ g\ x_1\ x_2\ \cdots\ x_n\ ]]$，只需要：

g <$> x1 <*> x2 <*> ... <*> xn

而pure函数的作用就是将一个不在上下文中的值（函数或参数）提升到上下文中，但不进行其他操作。比如参数$x_2$如果不在上下文中，需要用pure提升到上下文中才能按上面计算：

g <$> x1 <*> pure x2 <*> ... <*> xn

常用函数

liftA & liftA2 & liftA3

liftA :: Applicative f => (a -> b) -> f a -> f b

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d

不难推测liftA就是fmap，liftA2 f x1 x2相当于f <$> x1 <*> x2，liftA3 f x1 x2 x3相当于f <$> x1 <*> x2 <*> x3

<* & *>

类型类似函子的<$和$>：

(<*) :: Applicative f => f a -> f b -> f a

(*>) :: Applicative f => f a -> f b -> f b

<*接收两个函子，如果两个函子中又一个为空，就返回空，否则返回的类型与第一个函子相同。*>反过来

ghci> Just 3 <* Just 4
Just 3
ghci> Just 3 *> Just 4
Just 4
ghci> Nothing <* Just 3
Nothing
ghci> Nothing *> Just 3
Nothing
ghci> [1, 2, 3] <* [3, 4]
[1,1,2,2,3,3]
ghci> [1, 2, 3] *> [3, 4]
[3,4,3,4,3,4]
ghci> [] <* [1, 2, 3]
[]
ghci> [] *> [1, 2, 3]
[]

<**>

(**) :: Applicative f => f a -> f (a -> b) -> f b

接收的参数是<*>反转过来的，即先接收一个参数函子，然后接收一个函数函子，在将其应用返回。但是和flip(<*>)不同，它先取参数函子的每个参数，然后再取函数函子中的函数逐个应用：

ghci> [(+1), (+2), (+3)] <*> [1, 2]
[2,3,3,4,4,5]
ghci> [1, 2] <**> [(+1), (+2), (+3)]
[2,3,4,3,4,5]
ghci> flip(<*>) [1, 2] [(+1), (+2), (+3)]
[2,3,3,4,4,5]

when & unless

when :: Applicative f => Bool -> f () -> f ()

传入的第一个是一个结果为Bool类型的测试，如果测试为True，则调用第二个参数，否则返回pure ()。（when函数在上文IO操作中使用过）

unless则与when相反，测试为True返回pure ()

sequenceA

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

应用在列表上时，它的类型相当于：

[f a] -> f [a]

所以在列表上它的使用方法：

ghci> sequenceA [Just 3, Just 2, Just 1]  
Just [3,2,1]  
ghci> sequenceA [Just 3, Nothing, Just 1]  
Nothing  
ghci> sequenceA [(+3),(+2),(+1)] 3  
[6,5,4]  
ghci> sequenceA [[1,2,3],[4,5,6]]  
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]  
ghci> sequenceA [[1,2,3],[4,5,6],[3,4,4],[]]  
[]  

它在对同一个参数应用不同函数时很有用：

ghci> map (\f -> f 7) [(>4), (<10), odd]  
[True,True,True]  
ghci> sequenceA [(>4), (<10), odd] 7  
[True,True,True]  

Monad

单子（Monad）是对Applicative Functor的扩展（但是诞生比Applicative早），Functor的<$>函数实现了将普通函数应用在上下文值上，Applicative的<*>函数将上下文中函数应用在上下文值上。而Monad提供了一个函数>>=（bind），将一个接收普通值返回上下文值的函数应用在上下文值上：

class Applicative m => Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
    (>>) :: m a -> m b -> m b
    return :: a -> m a
    m >> n = m >>= \_ -> n
    return = pure

• return函数：和pure一样，只是有另一个名字
• >>函数：提供了默认的实现方法，它的作用和Applicative的*>函数一样
• >>=函数（bind）：比Applicative升级的函数，第一个参数是一个单子，第二个参数是一个接收值返回单子的函数，将这个函数应用在第一个参数单子中的值上，并返回得到的新单子

Monad实例

Maybe

Maybe是一个单子实例，Applicative已经为它实现了return，因此只需要>>=函数：

instance Monad Maybe where
    (Just x) >>= f = f x 
    Nothing  >>= _ = Nothing

根据定义就很容易实现Maybe的>>=函数了，而且也很好理解

ghci> Just 1 >>= \x -> Just (x + 1)
Just 2
ghci> Just 1 >>= \x -> return (x + 1)
Just 2
ghci> Nothing >>= \x -> Just (x + 1)
Nothing
ghci> Just 1 >>= \x -> Just (x + 1) >> Nothing >>= \y -> Just (y + 1)
Nothing

最后一个例子中出现了>> Nothing，这时Nothing前的部分全都相当于没用，因为>>操作符的左右两边只要有一个出现Nothing，那整体就会是Nothing。这个特性可以用于在中途随时判断失误，只要有一处失误，结果就会是Nothing

[]

列表也是一个单子：

instance Monad [] where
    xs >>= f = concat (map f xs)

将这个函数应用在xs的每个值上，将返回的所有列表平铺成一个列表：

ghci> [3,4,5] >>= \x -> [x,-x]  
[3,-3,4,-4,5,-5]  
ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)  
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]  

IO

IO也是一个单子，但是实现方法比较深奥（逃

(->) r

(->) r也是一个单子，和Functor、Applicative一样，先分析它的>>=类型签名：

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

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

也可以看出来，它接收两个函数f :: r -> a、g :: a -> r -> b，然后返回一个新的函数h :: r -> b

那么函数h接收一个类型为r的参数，返回一个类型为b的值。所以先对输入应用f得到类型为a的中间值，然后再将这个值和输入参数一起传入函数g得到结果。所以函数h的定义应该是：

\x -> g (f x) x

instance Monad ((->) r) where
    f >>= g = \x -> g (f x) x

ghci> (+3) >>= (+) $ 1
5
ghci> (+) <$> (+3) <*> id $ 1
5

do-notation

Haskell的do语句为链式的>>=应用提供了类似命令式（imperative style）的语法糖。比如a >>= \x -> b >> c >>= \y -> d：

a >>= \x ->
b >>
c >>= \y ->
d

其中有abcd四个值，可以看出a中内容绑定到了x上，c中内容绑定到了y上。使用do语句来表示这个操作可以写成：

do { x <- a 
   ;      b 
   ; y <- c 
   ;      d 
   }

其中的大括号和分号可以省略不写（挤在一行时不能省略）。do语句也只是一个语法糖，它可以递归地转换成普通的Monad操作语句：

• do e：e
• do { e; ... }：e >> do { … }
• do { v <- e; ... }：e >>= \v -> do { … }
• do { let ...; ... }：let … in do { … }

ApplicativeDo

比如如下一个do语句：

do x <- a 
   y <- b 
   z <- c 
   return (f x y z)

它可以转化成：

a >>= \x -> b >>= \y -> c >>= \z -> return (f x y z)

但是经过观察可以发现，整个语句实际上将函数f应用在了三个上下文中的值上，所以仅用Applicative的<$>和<*>完全可以实现：

f <$> a <*> b <*> c

而且在运行的时候Applicative的效率会比Monad高，所以Haskell会将do语句尽可能优先转换为Applicative的表示方法然后再计算

Monad Laws

1. Left identity： return a >>= k = k a
2. Right identity：m >>= return = m
3. Associativity：(m >>= g) >>= h = m >>= (\x -> g x >>= h)

前两个定律很好理解：

• 将a注入上下文之后绑定（bind）给函数k(:: a -> m a)，相当于直接将a直接传入函数k
• 将已经包含在上下文中的值绑定给return函数，相当于保持不变

第三个定律是结合律，把它写成更像结合律的表示方法是：

(m >>= (\x -> g x)) >>= h = m >>= (\x -> g x >>= h)

组合运算符（>=>）形式

Control.Monad模块中还定义了函数>=>（Kleisli-composition operator）：

infixr 1 >=>
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

使用>=>运算符可以将两个用于绑定的函数结合在一起。用它表示的Monad定律更加清晰直观：

1. Left identity：return >=> f = f
2. Right identity：f >=> return = f
3. Associativity：(f >=> g) >=> h = f >=> (g >=> h)

do-notation形式

Monad的这三个定律还可以使用do语句来描述：

1. Left identity：

   do { x' <- return x;
        f x'             =   do { f x } 
      }

2. Right identity：

   do { x <- m; 
        return x         =   do { m }
      }

3. Associativity：

   do { y <- do { x <- m;       do { x <- m;              do { x <- m;
                  f x                do { y <- f x;            y <- f x;
                }           =             g y         =        g y
        g y                             }                    }
      }                            }

Intuition

Monad也可以很自然地看成Applicative的升级版，比如Applicative的操作全部是固定的，而Monad的操作可以在中途突然改变

同时Monad也完成了Functor和Applicative无法完成的操作。比如要用fmap和实现>>=函数（即达成操作 m a -> (a -> m b) -> m b），先假设 f :: a -> m b，那么fmap f的类型就会是 m a -> m (m b)，将m a应用在fmap f上会得到结果m (m b)，而不是m b。但是目前只可以使用pure将一个值装入上下文中（a -> m a），而没有一个函数可以从上下文中提取值（m a -> a）。那么就需要定义一个新的函数来实现这个操作的效果（m (m b) -> m b）。因此Monad的另一个等效的定义方法是：

class Applicative m => Monad' m where
    join :: m (m a) -> m a 
    
    (>>=) :: m a -> (a -> m b) -> m b 
    x >>= f = join $ fmap f x

但是定义>>=函数会更为直观方便，所以Haskell采用了用>>=函数定义Monad的方法

同时Haskell还提供了join函数的定义：

join :: Monad m => m (m a) -> m a 
join x = x >>= id

常用函数

liftM & ap

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

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

所以liftM其实就是fmap、ap就是<*>，但是老版本的GHC定义Monad并没有Functor、Applicative的约束，所以实现了liftM、ap，并且保留了这个名字

因此一个单子也可以通过pure = return、(<*>) = ap直接成为应用函子的实例

sequence

sequence :: Monad m => [m a] -> m [a]

sequence的作用显而易见，而且在IO部分也使用到了。但是这个版本是在GHC.Base模块中定义的，还有一个更广泛的使用Traversable的定义在Data.Traversable模块中

replicateM

replicateM :: Applicative m => Int -> m a -> m [a]

mapM & forM

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

forM :: Monad m => [a] -> (a -> m b) -> m [b]

forM的用法在IO部分已经说过，mapM和forM都在Data.Traversable模块中有广泛版本

还有一些其他的函数：filterM、zipWithM、foldM、forever，通过名字就可以看出用法，是将原来仅使用与列表的函数提升至可以适用于所有单子

并且在函数名后加下划线，比如sequence_、mapM_，会忽略返回值（最终结果为m ()）

=<< & >=> & <=<

（>=>操作符在上面Monad Laws部分已经给出了定义）

• x >>= f = f =<< x
• f >=> g = g <=< f

MonadFail

MonadFail定义在Control.Monad.Fail模块中：

class Monad m => MonadFail m where
    fail :: String -> m a 

它只要求在Monad的基础上实现fail函数，接收一个字符串返回一个单子。这会使在do语句中产生错误时直接变为错误值（空值）使最终的返回值为错误值

MonadFail实例

instance MonadFail Maybe where
    fail _ = Nothing

instance MonadFail [] where
    fail _ = []

instance MonadFail IO where
    fail = failIO

Maybe和[]的fail函数都与第一个参数无关，直接返回空值（Nothing、[]）；而IO的fail函数直接使用failIO，实现方法也是深奥（接着逃

exampleFail :: Maybe Char 
exampleFail = do
    (x:xs) <- Just ""
    return x 

ghci> exampleFail
Nothing

在这个例子的do语句中，在提取Just “”中的值时用了模式匹配，但是因为其内容为空字符串，x:xs匹配会出现错误，这时就会触发fail函数直接返回Nothing

MonadFail Law

• fail s >>= m = fail s

Semigroup

半群（semigroup）是一个集合$S$，它需要指定一个二元运算符$\oplus$，并且满足

$$
a\oplus b \in S\quad a, b\in S
$$

以及结合（associative）律：

$$
(a\oplus b)\oplus c = a\oplus (b\oplus c)
$$

这个二元运算符在Haskell的Semigroup中被定义为<>函数：

class Semigroup a where
    (<>) :: a -> a -> a 

    sconcat :: NonEmpty a -> a 
    sconcat (a :| as) = go a as where 
        go b (c:cs) = b <> go c cs 
        go b []     = b
    
    stimes :: Integarl b => b -> a -> a 
    stimes = ...

除此之外还有sconcat和stimes函数，都给出了默认实现。对于列表，<>相当于(++)，stimes相当于concat . replicate：

ghci> [1, 2] <> [3, 4]
[1,2,3,4]
ghci> sconcat $ fromList [[1, 2], [3, 4]]
[1,2,3,4]
ghci> stimes 3 [1, 2]
[1,2,1,2,1,2]

Semigroup Law

• (x <> y) <> z = x <> (y <> z)

补：NonEmpty

NonEmpty表示非空列表，定义是：

data NonEmpty a = a :| [a] deriving (Eq, Ord)

使用一个元素和一个列表用:|连接就可以生成一个NonEmpty类型的列表

Data.List.NonEmpty模块中实现了很多普通列表有的函数，需要qualified import后调用，使用fromList、toList函数可以在普通列表和非空列表之间转换

ghci> import qualified Data.List.NonEmpty as NE
ghci> arr = NE.fromList [1, 2, 3]
ghci> arr
1 :| [2,3]
ghci> NE.head arr 
1
ghci> NE.tail arr 
[2,3]

Monoid

幺半群（Monoid）是一个有单位元素$e$的半群，即$e$满足：

$$
e\oplus x = x\oplus e = x
$$

class Semigroup a => Monoid a where 
    mempty  :: a 
    
    mappend :: a -> a -> a 
    mappend = (<>)

    mconcat :: [a] -> a 
    mconcat = foldr mappend mempty 

可以看出Monoid要求了三个函数，其中最少只需要mempty，它直接返回一个值，表示单位元素。mappend即Semigroup中的<>运算符，mconcat也提供了默认实现

实例

[a]

因为Monoid的实例是一个具体类型，而不是像Functor等一样等类型构造器，所以[]并不是Monoid的实例，但是具体类型[a]是一个幺半群：

instance Semigroup [a] where 
    (<>) = (++)

instance Monoid [a] where 
    mempty = [] 
    mconcat xss = [x | xs <- xss, x <- xs]

列表的单位元素(mempty)就是空列表[]，运算符就是合并列表(++)，mconcat也用列表推导重新实现提高效率

ghci> mempty :: [Int] 
[]
ghci> [1, 2] <> [3, 4]
[1,2,3,4]
ghci> [1, 2] `mappend` [3, 4]
[1,2,3,4]
ghci> mconcat [[1,2], [3,4]]
[1,2,3,4]

Ordering

instance Semigroup Ordering where
    LT <> _ = LT
    EQ <> y = y
    GT <> _ = GT

instance Monoid Ordering where
    mempty = EQ

主要可以用于比较字典序：

ghci> mconcat (zipWith compare "abcd" "acbd")
LT

Sum & Product

对于数字，加法和乘法都满足结合律，所以对于Num，有两种实现Monoid的方式，但是不能为同一类型设置两种实例方式，所以Data.Monoid中提供了两个包装器————Sum和Product：

newtype Sum a = Sum {getSum :: a} deriving (...)
newtype Product a = Product {getProduct :: a} deriving (...)

它们使用Sum或Product来包装起一个数字，可以通过getSum或getProduct来获取其中的值

对于加法，二元操作为(+)，单位元素为0；对于乘法，二元操作为(*)，单位元素为1:

instance Num a => Semigroup (Sum a) where
    (<>) = coerce ((+) :: a -> a -> a)

instance Num a => Monoid (Sum a) where
    mempty = Sum 0

instance Num a => Semigroup (Product a) where
    (<>) = coerce ((*) :: a -> a -> a)

instance Num a => Monoid (Product a) where
    mempty = Product 1

ghci> Sum 5 <> Sum 6 <> Sum 10
Sum {getSum = 21}
ghci> getSum . mconcat . fmap Sum $ [5, 6, 10]
21
ghci> Product 5 <> Product 6 <> Product 10
Product {getProduct = 300}
ghci> getProduct . mconcat . fmap Product $ [5, 6, 10]
300

All & Any

和数字一样，布尔值也有两种实现Monoid的方式，因此Data.Monoid模块中也提供了两个包装器，分别实现了这两种Monoid：

newtype All = All { getAll :: Bool } deriving (...)

instance Semigroup All where
        (<>) = coerce (&&)

instance Monoid All where
        mempty = All True


newtype Any = Any { getAny :: Bool } deriving (...)

instance Semigroup Any where
        (<>) = coerce (||)

instance Monoid Any where
        mempty = Any False

ghci> getAll (All True <> mempty <> All False)
False
ghci> getAll (mconcat (map (\x -> All (even x)) [2,4,6,7,8]))
False
ghci> getAny (Any True <> mempty <> Any False)
True
ghci> getAny (mconcat (map (\x -> Any (even x)) [2,4,6,7,8]))
True

Monoid a => Maybe a

如果a是一个(幺)半群，那么Maybe a也是一个幺半群，单位元就是Nothing：

instance Semigroup a => Semigroup (Maybe a) where
    Nothing <> b       = b
    a       <> Nothing = a
    Just a  <> Just b  = Just (a <> b)

instance Semigroup a => Monoid (Maybe a) where
    mempty = Nothing

ghci> Nothing <> Just "andy"
Just "andy"
ghci> Just LT <> Nothing
Just LT
ghci> Just (Sum 3) <> Just (Sum 4) 
Just (Sum {getSum = 7})

First & Last

对于Maybe也有两种实现Monoid的方法，即<>操作每次恒取左边和每次恒取右边（在没有Nothing的情况下），所以Data.Monoid模块中也提供了两个新的包装器：First和Last：

newtype First a = First { getFirst :: Maybe a } deriving (...)

instance Semigroup (First a) where
    First Nothing <> b = b
    a             <> _ = a

instance Monoid (First a) where
    mempty = First Nothing


newtype Last a = Last { getLast :: Maybe a } deriving (...)

instance Semigroup (Last a) where
    a <> Last Nothing = a
    _ <> b            = b

instance Monoid (Last a) where
    mempty = Last Nothing

ghci> getFirst (First (Just "hello") <> First Nothing <> First (Just "world"))
Just "hello"
ghci> getLast (Last (Just "hello") <> Last Nothing <> Last (Just "world"))
Just "world"
ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]  
Just 9
ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]  
Just 10

Min & Max

对于有界的类型，也有两种实现Monoid的方式，每次二元操作都取最小或最大。Data.Semigroup模块中提供了两个包装其器：Min和Max：

newtype Min a = Min { getMin :: a } deriving (...)

instance Ord a => Semigroup (Min a) where
    (<>) = coerce (min :: a -> a -> a)

instance (Ord a, Bounded a) => Monoid (Min a) where
    mempty = maxBound


newtype Max a = Max { getMax :: a } deriving (...)

instance Ord a => Semigroup (Max a) where
    (<>) = coerce (max :: a -> a -> a)

instance (Ord a, Bounded a) => Monoid (Max a) where
    mempty = minBound

ghci> Min 3 <> Min 5
Min {getMin = 3}
ghci> Max 3 <> Max 5
Max {getMax = 5}
ghci> getMin . mconcat . map Min $ [1,2,3] :: Int
1
ghci> getMax . mconcat . map Max $ [1,2,3] :: Int
3

元组

当元组内的所有元素都是幺半群时，整个元组也是一个幺半群：

instance (Semigroup a, Semigroup b) => Semigroup (a, b) where
        (a,b) <> (a',b') = (a<>a',b<>b')
        stimes n (a,b) = (stimes n a, stimes n b)

instance (Monoid a, Monoid b) => Monoid (a,b) where
        mempty = (mempty, mempty)

ghci> mconcat $ map (\x -> (Min x, Max x)) [1..10] :: (Min Int, Max Int)
(Min {getMin = 1},Max {getMax = 10})

Monoid Laws

• mempty <> x = x
• x <> mempty = x
• (x <> y) <> z = x <> (y <> z)

Monoidal classes

Applicative、Monad、Arrow都有有幺半群性质的子类型类，分别是Alternative、MonadPlus、ArrowPlus

Alternative

class Applicative f => Alternative f where
    -- | The identity of '<|>'
    empty :: f a
    -- | An associative binary operation
    (<|>) :: f a -> f a -> f a

    some :: f a -> f [a]
    some v = (:) <$> v <*> many v
    many :: f a -> f [a]
    many v = some v <|> pure []

其中empty是幺半群中的单位元素，<|>是幺半群中的二元运算符。some和many是两个函数（意义还不懂）

Alternative实例

[]

instance Alternative [] where
    empty = []
    (<|>) = (++)

和Monoid一样，单位元素是空列表，二元运算是列表合并

ghci> [1,2,3] <|> empty <|> [4,5]
[1,2,3,4,5]
ghci> some []
[]
ghci> many []
[[]]

Maybe

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

Maybe作为Alternative的单位元素是Nothing，二元运算是始终取左边（当左边不为Nothing时）

ghci> Nothing <|> Just 1 <|> Just 2 
Just 1 
ghci> some Nothing
Nothing 
ghci> many Nothing 
Just []

ZipList

instance Alternative ZipList where
   empty = ZipList []
   ZipList xs <|> ZipList ys = ZipList (xs ++ drop (length xs) ys)

<>getZipList $ ZipList [1,2] <|> ZipList [3,4,5,6]
[1,2,5,6]
<>getZipList $ ZipList [1,2,3,4] <|> ZipList [3,4,5,6]
[1,2,3,4]

Alternative Laws

• Monoid laws:

  empty <|> x = x 
  x <|> empty = x 
  (x <|> y) <|> z = x <|> (y <|> z)

• Left zero law：empty <*> f = empty
  以上的定律是都满足都，下面的定律只有部分满足：
• Right zero law：f <*> empty = empty （大部分包括Maybe、[]满足，IO不满足）
• Left distribution：(a <|> b) <*> c = (a <*> c) <|> (b <*> c) （Maybe、[]满足，IO及大部分parsers不满足）
• Right distribution：a <*> (b <|> c) = (a <*> b) <|> (a <*> c) （大部分不满足，但Maybe满足）
• Left catch：(pure a) <|> x = pure a （Maybe、IO、parsers满足，但[]不满足）

常用函数

• asum :: (Foldable t, Alternative f) => t (f a) -> f a，相当于foldr (<|>) empty：

  ghci> asum [Nothing, Just 5, Just 3]
  Just 5
  ghci> asum [[2],[3],[4,5]]
  [2,3,4,5]

• guard :: (Alternative f) => Bool -> f ()：

  guard True  = pure ()
  guard False = empty 

MonadPlus

class (Alternative m, Monad m) => MonadPlus m where
   mzero :: m a
   mzero = empty

   mplus :: m a -> m a -> m a
   mplus = (<|>)

MonadPlus实例

[]、Maybe都是MonadPlus的实例，mzero和mplus都由Alternative实现

MonadPlus Laws

• Monoid laws
• Left zero：mzero >>= f = mzero
• Right zero：m >> mzero = mzero

常用函数

• msum = asum
• mfilter：

  mfilter p ma = do
      a <- ma
      if p a then return a else mzero

ArrowPlus

ArrowZero和ArrowPlus分别为Arrow设置了Monoid中的单位元素和二元运算符，使之成为了一个幺半群：

class Arrow arr => ArrowZero arr where
    zeroArrow :: b `arr` c

class ArrowZero arr => ArrowPlus arr where
    (<+>) :: (b `arr` c) -> (b `arr` c) -> (b `arr` c)

一些其它typeclasses

Foldable

Foldable是表示可以折叠（fold）的类型类，在Data.Foldable中定义，这使得和fold相关的函数可以用在任意Foldable的实例类型上。它的定义是：

class Foldable t where
    fold     :: Monoid m => t m -> m
    foldMap  :: Monoid m => (a -> m) -> t a -> m
    foldMap' :: Monoid m => (a -> m) -> t a -> m
    foldr    :: (a -> b -> b) -> b -> t a -> b
    foldr'   :: (a -> b -> b) -> b -> t a -> b
    foldl    :: (b -> a -> b) -> b -> t a -> b
    foldl'   :: (b -> a -> b) -> b -> t a -> b
    foldr1   :: (a -> a -> a) -> t a -> a
    foldl1   :: (a -> a -> a) -> t a -> a
    toList   :: t a -> [a]
    null     :: t a -> Bool
    length   :: t a -> Int
    elem     :: Eq a => a -> t a -> Bool
    maximum  :: Ord a => t a -> a
    minimum  :: Ord a => t a -> a
    sum      :: Num a => t a -> a
    product  :: Num a => t a -> a
    {-# MINIMAL foldMap | foldr #-}

最少只要实现foldr和foldMap其中之一就可以使一个类型成为Foldable的实例，其它的函数都有由这两个函数提供的默认实现，而且这两个函数之间也有相互实现。因此只要实现foldr或foldMap一个函数就可以使用所有其它Foldable中的函数。foldr函数在前面已经有学过，foldMap的例子是：

ghci> foldMap Sum [1, 3, 5]
Sum {getSum = 9}
ghci> foldMap Product [1, 3, 5]
Product {getProduct = 15}
ghci> foldMap (replicate 3) [1, 2, 3]
[1,1,1,2,2,2,3,3,3]

Foldable实例

[]、Maybe、Either a、(,) a都是Foldable的实例，标准容器库中的Map、Set等也都是Foldable的实例。也可以自定义二叉树类型，并使其成为Foldable的实例：

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

instance Foldable Tree where 
    foldMap :: Monoid m => (a -> m) -> Tree a -> m
    foldMap f Empty        = mempty
    foldMap f (Leaf x)     = f x
    foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r

常用函数

• asum :: (Alternative f, Foldable t) => t (f a) -> f a，用<|>逐个连接所有元素
• sequenceA_ :: (Applicative f, Foldable t) => t (f a) -> f ()，由于丢弃结果，所以Foldable t就可以满足；因此不同于sequenceA需要Traversable
• traverse_ :: (Applicative f, Foldable t) => (a -> f b) -> t a -> f ()
• for_ :: (Applicative f, Foldable t) => t a -> (a -> f b) -> f ()

Traversable

Traversable是表示可遍历的类型类，在Data.Traversable模块中定义，它是Foldable的升级版，同时也是一个Functor，它的定义是：

class (Functor t, Foldable t) => Traversable t where 
    traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
    sequenceA :: Applicative f => t (f a) -> f (t a)
    mapM      ::       Monad m => (a -> m b) -> t a -> m (t b)
    sequence  ::       Monad m => t (m a) -> m (t a)
    {-# MINIMAL traverse | sequenceA #-}

最少只需要实现traverse函数或者sequenceA函数。其中各个函数的功能通过类型签名也都能推测出来。但是其中mapM就是traverse，sequence就是sequenceA，它们存在只是历史遗留（

Traversable实例

instance Traversable Maybe where
    traverse _ Nothing = pure Nothing
    traverse f (Just x) = Just <$> f x

instance Traversable [] where
    {-# INLINE traverse #-}
    traverse f = foldr cons_f (pure [])
      where cons_f x ys = liftA2 (:) (f x) ys

instance Traversable (Either a) where
    traverse _ (Left x) = pure (Left x)
    traverse f (Right y) = Right <$> f y

instance Traversable ((,) a) where
    traverse f (x, y) = (,) x <$> f y

...

上面的Tree也可以成为Traversable的实例：

instance Functor Tree where
    fmap :: (a -> b) -> Tree a -> Tree b
    fmap     g Empty        = Empty
    fmap     g (Leaf x)     = Leaf $ g x
    fmap     g (Node l x r) = Node (fmap g l)
                                   (g x)
                                   (fmap g r)

instance Traversable Tree where
    traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b) 
    traverse g Empty        = pure Empty
    traverse g (Leaf x)     = Leaf <$> g x
    traverse g (Node l x r) = Node <$> traverse g l
                                   <*> g x
                                   <*> traverse g r

Traversable Laws

Traversable也有两条定律：

1. traverse Identity = Identity
2. traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

其中Identity和Compose分别定义在Data.Functor.Identity和Data.Functor.Compose两个模块中：

newtype Identity a = Identity { runIdentity :: a } deriving (...)
newtype Compose f g a = Compose { getCompose :: f (g a) } deriving (...)

Bifunctor

Functor的实例的kind都是* -> *，因此fmap只能将一个函数映射到一个值上。而Bifunctor（在Data.Bifunctor模块中定义）的实例的kind是* -> * -> *，而且它的bimap可以同时将两个函数映射到两个值上：

class Bifunctor p where 
    bimap  :: (a -> b) -> (c -> d) -> p a c -> p b d 
    first  :: (a -> b) -> p a c -> p b c 
    second :: (b -> c) -> p a b -> p a c 
    {-# MINIMAL bimap | first, second #-}

同时bimap和first,second之间也可以相互转换：

bimap f g = first f . second g

first  f = bimap f id
second g = bimap id g

对于Functor，((,) e)和Either e才是Functor的实例，因为他们是* -> *。但是对于Bifunctor，(,)和Either就是Bifunctor的实例：

ghci> bimap (+1) length (4, [1,2,3])
(5,3)

Bifunctor Laws

1. bimap id id = id
   first id = id
   second id = id
2. bimap (f . g) (h . i) = bimap f h . bimap g i
   first (f . g) = first f . first g
   second (f . g) = second f . second g

Category

Haskell中的Category将一般的函数推广到了普遍的态射上，它在Control.Category模块中，定义是：

class Category cat where 
    id  :: cat a a 
    (.) :: cat b c -> cat a b -> cat a c

它的实例有(->)和Kleisli m：

instance Category (->) where
    id = GHC.Base.id
    (.) = (GHC.Base..)

Kleisli是一个范畴，用来表示函数a -> m b，Haskell中，它在Control.Arrow模块中定义：

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Monad m => Category (Kleisli m) where
    id :: Kleisli m a a
    id = Kleisli return

    (.) :: Kleisli m b c -> Kleisli m a b -> Kleisli m a c
    Kleisli g . Kleisli h = Kleisli (h >=> g)

Category要满足的定律只有id是(.)操作的单位元，以及(.)操作是可结合的

同时Category还提供了两个函数<<<和>>>：

(<<<) :: Category cat => cat b c -> cat a b -> cat a c
(<<<) = (.)

(>>>) :: Category cat => cat a b -> cat b c -> cat a c 
f >>> g = g . f 

Arrow

Arrow将函数进一步抽象化，它定义在Control.Arrow模块中：

class Category a => Arrow a where 
    arr    :: (b -> c) -> a b c 
    first  :: a b c -> a (b, d) (c, d)
    second :: a b c -> a (d, b) (d, c)
    (***)  :: a b c -> a b' c' -> a (b, b') (c, c')
    (&&&)  :: a b c -> a b c' -> a b (c, c')
    {-# MINIMAL arr, (first | (***)) #-}

其中：

• arr函数将一个函数变成一个Arrow
• first函数将一个Arrow变成一个二元组间的Arrow，且只会对一个元素进行操作，第二个元素保持不变
• second函数与first相反，第一个元素保持不变
• ***函数是Arrow之间的parallel composition，对于函数: (g *** h) (x, y) = (g x, h y)
• &&&函数是Arrow之间的fanout composition，对于函数: (g &&& h) x = (g x, h x)

它的实例也有(->)和Kleisli：

instance Arrow (->) where
  arr :: (b -> c) -> (b -> c)
  arr g = g

  first :: (b -> c) -> ((b,d) -> (c,d))
  first g (x,y) = (g x, y)

instance Monad m => Arrow (Kleisli m) where
  arr :: (b -> c) -> Kleisli m b c
  arr f = Kleisli (return . f)

  first :: Kleisli m b c -> Kleisli m (b,d) (c,d)
  first (Kleisli f) = Kleisli (\ ~(b,d) -> do c <- f b
                                              return (c,d) )

常用函数：

returnA :: Arrow a => a b b
returnA = arr id

(^>>) :: Arrow a => (b -> c) -> a c d -> a b d
f ^>> a = arr f >>> a

(>>^) :: Arrow a => a b c -> (c -> d) -> a b d
a >>^ f = a >>> arr f

(<<^) :: Arrow a => a c d -> (b -> c) -> a b d
a <<^ f = a <<< arr f

(^<<) :: Arrow a => (c -> d) -> a b c -> a b d
f ^<< a = arr f <<< a

Arrow notation

类似do-notation，Arrow也提供了一套方便的语句：

proc x -> do 
    y <- action1 -< ... 
    z <- action2 -< ...
    returnA -< ...

其中proc代替了lambda表达式中的斜杠\，-<右边的为输入，左边的为接收输入的函数。比如，下面三种写法达成的效果是一样的：

f :: Int -> (Int, Int)
f = \x ->
    let y  = 2 * x
        z1 = y + 3
        z2 = y - 5
    in (z1, z2) 
-- ghci> f 10 
-- (23,15)

fM :: Int -> Identity (Int, Int)
fM = \x -> do
    y  <- return (2 * x)
    z1 <- return (y + 3)
    z2 <- return (y - 5)
    return (z1, z2)

-- ghci> runIdentity (fM 10)
-- (23,15)

fA :: Int -> (Int, Int)
fA = proc x -> do
    y  <- (2 *) -< x
    z1 <- (+ 3) -< y
    z2 <- (subtract 5) -< y
    returnA -< (z1, z2)

-- ghci> fA 10
-- (23,15)

ArrowChoice

class Arrow a => ArrowChoice a where
    left :: a b c -> a (Either b d) (Either c d)
    left = (+++ id)

    right :: a b c -> a (Either d b) (Either d c)
    right = (id +++)

    (+++) :: a b c -> a b' c' -> a (Either b b') (Either c c')
    f +++ g = left f >>> arr mirror >>> left g >>> arr mirror
      where
        mirror :: Either x y -> Either y x
        mirror (Left x) = Right x
        mirror (Right y) = Left y

    (|||) :: a b d -> a c d -> a (Either b c) d
    f ||| g = f +++ g >>> arr untag
      where
        untag (Left x) = x
        untag (Right y) = y

instance ArrowChoice (->) where
    left f = f +++ id
    right f = id +++ f
    f +++ g = (Left . f) ||| (Right . g)
    (|||) = either

instance Monad m => ArrowChoice (Kleisli m) where
    left f = f +++ arr id
    right f = arr id +++ f
    f +++ g = (f >>> arr Left) ||| (g >>> arr Right)
    Kleisli f ||| Kleisli g = Kleisli (either f g)

ArrowZero & ArrowPlus

class Arrow a => ArrowZero a where
    zeroArrow :: a b c

class ArrowZero a => ArrowPlus a where
    (<+>) :: a b c -> a b c -> a b c

instance MonadPlus m => ArrowZero (Kleisli m) where
    zeroArrow = Kleisli (\_ -> mzero)

instance MonadPlus m => ArrowPlus (Kleisli m) where
    Kleisli f <+> Kleisli g = Kleisli (\x -> f x `mplus` g x)

例子

ghci> runKleisli ((Kleisli (\x -> [x * 2])) <+> (Kleisli (\x -> [x, -x]))) 2
[4,2,-2]
ghci> either (+2) (*3) (Left 3)
5
ghci> either (+2) (*3) (Right 3)
9
ghci> (+2) ||| (*3) $ (Left 3)
5
ghci> (+2) +++ (*3) $ (Left 3)
Left 5
ghci> (+2) ||| (*3) $ (Right 3)
9
ghci> (+2) +++ (*3) $ (Right 3)
Right 9
ghci> left (+2) (Left 3)
Left 5
ghci> right (*3) (Right 3)
Right 9
ghci> left (+2) (Right 3)
Right 3
ghci> right (*3) (Left 3)
Left 3
ghci> runKleisli ((Kleisli (\x -> [x * 2])) ||| (Kleisli (\x -> [x, -x]))) (Left 3)
[6]
ghci> runKleisli ((Kleisli (\x -> [x * 2])) ||| (Kleisli (\x -> [x, -x]))) (Right 3)
[3,-3]
ghci> runKleisli ((Kleisli (\x -> [x * 2])) +++ (Kleisli (\x -> [x, -x]))) (Left 3)
[Left 6]
ghci> runKleisli ((Kleisli (\x -> [x * 2])) +++ (Kleisli (\x -> [x, -x]))) (Right 3)
[Right 3,Right (-3)]

Haskell与范畴论

Haskell中的函子单子等都与范畴论（category theory）有很多联系，所以打算简单了解一下范畴论的相关内容。

范畴论是数学的一门学科，以抽象的方法处理数学概念，将这些概念形式化成一组组的“物件”及“态射”。数学中许多重要的领域可以形式化为范畴。使用范畴论可以令这些领域中许多难理解、难捉摸的数学结论更容易叙述证明。

———— 维基百科

范畴（Category）

范畴本质上是一个简单的集合，一个范畴$\mathbf{C}$包含三个组成成分：

• 一个类$\mathrm{ob}(\mathbf{C})$：其中元素称为对象（objects）
• 一个类$\mathrm{hom}(\mathbf{C})$：其中元素称为态射（morphisms）（或箭号（arrows））：每个态射连接了两个对象：源对象（source object）、目标对象（target object）。如果$f$是从源对象$A$到目标对象$B$（$A, B\in \mathrm{ob}(\mathbf{C})$）的态射，那么记为$f : A\to B$
• 一个二元运算，称为态射复合（composition）：两个态射$g : A\to B$、$f : B\to C$的复合记为$f\circ g : A\to C$
  在Haskell和大部分数学理论中都是从右向左计算，即$f\circ g$中是先计算$g : A\to B$再计算$f : B\to C$

许多东西都可以组成范畴。比如:

 $\mathbf{Set}$是一个范畴，对象为所有集合，态射为集合之间的函数，复合即函数之间的复合

 $\mathbf{Grp}$是一个范畴，对象为所有群，态射为群同态（group homomorphisms），例如对于群$(G,*)$和$(H,\cdot )$，有群同态$h : (G,*)\to (H,\cdot )$，则需要对于$G$中的任意元素$u,v$满足
$$h(u*v)=h(u)\cdot h(v)$$

注意：态射不必须为函数；而且可以存在源对象和目标对象都相同的不同态射

范畴公理

每个范畴都需要满足三条定律：

1. 态射复合需要满足结合律（associativity）：
   $$f\circ (g\circ h) = (f\circ g)\circ h$$
2. 范畴在复合操作下是闭合的（closed）：
      如果范畴$\mathbf{C}$中存在态射$f : B\to C$、$g : A\to B$，那么范畴$\mathbf{C}$中也一定存在态射$h : A\to C$，且$h=f\circ g$
3. 每个对象都需要有单位态射（identity morphisms）：
      对于范畴$\mathbf{C}$中的对象$A$，一定存在单位态射$\mathrm{id}_A : A\to A$，且对于每个态射$g : A\to B$，一定有：
   $$g\circ\mathrm{id}_A = \mathrm{id}_B\circ g = g$$

$\mathbf{Hask}$范畴

范畴$\mathbf{Hask}$的对象为Haskell中的类型（types），态射是Haskell中的函数，复合运算是(.)。即从类型A到类型B的函数 f :: A -> B 就是$\mathbf{Hask}$范畴中的一个态射。而函数 f :: B -> C 、g :: A -> B 的组合 f . g 就是一个新的函数 h :: A -> C。

对于三条定律：

1. 第一条显然满足：f . (g . h) = (f . g) . h
2. 第二条也显然满足，如果有函数 f :: B -> C 、g :: A -> B，一定有函数 h = (f . g) :: A -> C
3. 对于第三条定律，Haskell中存在单位函数 id ，但id是多态（polymorphic）的，要为其指定类型使其变成单态（monomorphic）的。比如态射$\mathrm{id}_A$在Haskell中就可以表示为 id :: A -> A。并且显然满足第三条定律（其中 f :: A -> B）：

   (id :: B -> B) . f = f . (id :: A -> A) = f

函子（Functors）

一个范畴中的态射将两个对象联系起来，而函子则会将两个范畴联系起来。换句话说，函子就是从一个范畴到另一个范畴的变换。比如对于范畴$\mathbf{C}$、$\mathbf{D}$，定义函子$F : \mathbf{C}\to\mathbf{D}$满足：

• 对于$\mathbf{C}$中的任意对象$A$，在$\mathbf{D}$中都有对象$F(A)$
• 对于$\mathbf{C}$中的任意态射$f : A\to B$，在$\mathbf{D}$中都有态射$F(f) : F(A)\to F(B)$

比如：

 遗忘函子（forgetful functor）$U : \mathbf{Grp}\to\mathbf{Set}$，将一个群映射到一个集合中，将群同态映射到集合间的函数

 幂集函子（power set functor）$P : \mathbf{Set}\to\mathbf{Set}$，将一个集合映射到它的幂集，将原集合中的函数$f : A\to B$映射到函数$P(f) : \mathcal{P}(A)\to\mathcal{P}(B)$，即从$U\subseteq A$到值域$f(U)\subseteq B$的映射

 自函子（endofunctor）$1_{\mathbf{C}} : \mathbf{C}\to\mathbf{C}$，将一个范畴映射到它本身

函子公理

函子$F : \mathbf{C}\to\mathbf{D}$也需要满足两个公理：

1. 对于任意对象$X\in\mathbf{C}$，恒有$F(\mathrm{id}_X)=\mathrm{id}_{F(X)}$
2. 对于态射$f : Y\to Z$、$g : X\to Y$，恒有$F(f\circ g) = F(f)\circ F(g)$

$\mathbf{Hask}$范畴上的函子

Haskell中的Functor定义是：

class Functor (f :: * -> *) where 
    fmap :: (a -> b) -> f a -> f b

对于Haskell中的Functor，它实际上是从$\mathbf{Hask}$范畴（types）到它子范畴的变换。比如列表函子$\mathtt{[]} : \mathbf{Hask}\to\mathbf{Lst}$（其中$\mathbf{Lst}$是所有Haskell中列表类型构成的范畴）

它也达成了范畴论中对于函子的要求。函子需要进行两个操作：将一个范畴中的对象映射到另一个范畴中、将一个范畴中的态射映射到另一个范畴中。以Maybe为例，它实现了函子的要求：

1. Maybe是一个类型构造器，他可以将任意类型 T 变成新类型 Maybe T，相当于从$\mathbf{Hask}$范畴的对象变成了$\mathbf{Maybe}$范畴的对象
2. fmap函数接收一个 a -> b 类型的函数，返回一个 Maybe a -> Maybe b 类型的函数，相当于将$\mathbf{Hask}$范畴中的态射$f : A\to B$映射成了$\mathbf{Maybe}$范畴中的态射$\mathbf{Maybe}(f) : \mathbf{Maybe}(A)\to\mathbf{Maybe}(B)$

注意：时刻记住这里研究的是$\mathbf{Hask}$范畴和它的子范畴，对象是类型而不是值，态射是函数也指的是从类型到类型

同时，Haskell中的Functor也满足函子公理：

1. fmap id = id 即 fmap (id :: A -> A) = (id :: f A -> f A)
2. fmap (f . g) = fmap f . fmap g

单子（Monads）

一个单子说白了不过就是自函子范畴上的一个幺半群而已 _(:з」∠)_

自函子在前面说到过是从一个范畴到自身的一个函子，如范畴$\mathbf{C}$上的自函子是$F : \mathbf{C}\to\mathbf{C}$。自函子范畴就是对象都是自函子的范畴。幺半群和Haskell中学到的Monoid类型类一样，是一个有可结合二元运算和单位元的代数结构。因此单子就是一个自函子，而且它有可结合二元运算（Haskell中>=>）和单位元（Haskell中return）。

一个单子$M : \mathbf{C}\to\mathbf{C}$还包含两个态射（对于范畴$\mathbf{C}$中的所有对象$X$）：

1. $\mathrm{unit}_X^M : X\to M(X)$
2. $\mathrm{join}_X^M : M(M(X))\to M(X)$

（当式子中的单子明显是$M$时，可以省略上标${}^M$）

Haskell中Monad的定义是：

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

其中很显然多态函数return对应了定义中的$\mathrm{unit}$，但是>>=和$mathrm{join}$的对应关系并不明显。因此Haskell中有一个工具函数join，它的效果就是定义中的$\mathrm{join}$，而且它可以和>>=互相定义：

join :: Monad m => m (m a) -> m a
join x = x >>= id

(>>=) :: m a -> (a -> m b) -> m b 
x >>= f = join $ fmap f x

所以Haskell中为Monad要求定义>>=就相当于定义了$\mathrm{join}$

例如，幂集函子$P : \mathbf{Set}\to\mathbf{Set}$也是一个单子，可以为它定义$\mathrm{unit}$和$\mathrm{join}$两个态射。Haskell中的列表也可以近似看作幂集函子。

 态射/函数的类型：

幂集函子	Haskell中列表
一个集合$S$和一个态射$f : A\to B$	一个类型 T 和一个函数 f :: A -> B
$P(f) : \mathcal{P}(A)\to\mathcal{P}(B)$	fmap f :: [A] -> [B]
$\mathrm{unit}_S : S\to\mathcal{P}(S)$	return :: T -> [T]
$\mathrm{join}_S : \mathcal{P}(\mathcal{P}(S))\to\mathcal{P}(S)$	join :: [[T]] -> [T]

 态射/函数的定义：

幂集函子	Haskell中列表
$(\mathcal{P}(f))(S) = \{f(a):a\in S\}$	fmap f xs = [ f a | a <- xs ]
$\mathrm{unit}_S(x) = \{x\}$	return x = [x]
$\mathrm{join}_S(L) = \bigcup L$	join xs = concat xs

单子公理

给定一个单子$M : \mathbf{C}\to\mathbf{C}$，和一个态射$f : A\to B$（其中$A,B\in \mathbf{C}$），那么满足下面四条定律：

1. $\mathrm{join}\circ M(\mathrm{join})=\mathrm{join}\circ\mathrm{join}$
2. $\mathrm{join}\circ M(\mathrm{unit})=\mathrm{join}\circ\mathrm{unit}=\mathrm{id}$
3. $\mathrm{unit}\circ f = M(f)\circ\mathrm{unit}$
4. $\mathrm{join}\circ M(M(f)) = M(f)\circ\mathrm{join}$

也可以很自然地将其转化为Haskell中的表述：

1. join . fmap join = join . join
2. join . fmap return = join . return = id
3. return . f = fmap f . return
4. join . fmap (fmap f) = fmap f . join

在Haskell中，使用>>=也有三个定律和这四个定律是等价的：

1. return x >>= f = f x

     return x >>= f 
   = join (fmap f (return x)) = join (fmap f . return $ x)
   = join (return (f x)) = join (return . f $ x)
   = join . return $ (f x)
   = id (f x)
   = f x

2. m >>= return = m

     m >>= return 
   = join (fmap return m) = join . fmap return $ m 
   = id m
   = m 

3. (m >>= f) >>= g = m >>= (\x -> f x >>= g)

     (m >>= f) >>= g 
   = (join (fmap f m)) >>= g = join (fmap g (join (fmap f m)))
   = join . fmap g . join $ fmap f m 
   = join . join . fmap (fmap g) $ fmap f m 
   = join . join . fmap (fmap g) . fmap f $ m 
   = join . join . fmap (fmap g . f) $ m 
   = join . fmap join . fmap (fmap g . f) $ m 
   = join . fmap (join . (fmap g . f)) $ m 
   = join . fmap (\x -> join (fmap g (f x))) $ m 
   = join . fmap (\x -> f x >>= g) $ m 
   = join (fmap (\x -> f x >>= g) m)
   = m >>= (\x -> f x >>= g)

有关do语句和>=>的公理表述在上文中已经说过

后记

啃了将近一个月，算是把Haskell的主要内容都啃完了。主要就是前期看Learn You a Haskell，后期看Typeclassopedia，都是pdcxs推荐给的教程。但是一堆视频一个都没有耐心看进去qwq

后面的部分的理解感觉也没到位，Category、Arrow等这些类型类也就是大致地看了一眼，甚至有什么用都不太清楚_(:з」∠)_

感觉Haskell这门语言确实很神奇，很多语法都很有意思，而且可以做到非常贴近数学、贴近数学概念。学的时候也是越学坑越多，先是函数式编程引申到了lambda演算，然后是函子等一系列概念引申到了范畴论，目前范畴论简单地看了一部分，lambda演算也没深入研究，以后有时间再说了（咕咕咕）

现在感觉我学到的Haskell简直是皮毛，还有一堆源码里的东西不知道是怎么回事（包括但不限于#，~），也还有一堆类型类和用法没有学到（包括但不限于Monad Transformer、Writer、Reader、State、Comonad、MonadFix、Lens、Parsec、……）md，这么一看差的还真多，以后有时间再慢慢学了，这个假期还有好多其它事要干呢，Haskell这边先摸了_(:з」∠)_

Reference

• Learn You a Haskell
• Writing foldl using foldr - StackOverflow
• Haskell：用foldr定义foldl
• Typeclassopedia - Haskell wiki
• Hoogle
• Functors, Applicatives, And Monads In Pictures
• Haskell学习 - functor
• Haskell语言学习笔记（8）Monoid - zwvista
• Haskell语言学习笔记（16）Alternative - zwvista
• Haskell语言学习笔记（40）Arrow（1） - zwvista
• 24 Days of GHC Extensions: Arrows - Tom Ellis
• Haskell语言学习笔记（47）Arrow（2） - zwvista
• Haskell/Category theory - wikibooks
• Category theory - wikipedia
• 范畴论 - 维基百科
• Monad (category theory) - wikipedia
• Functor - wikipedia

"The End?"