Haskell 的学习曲线和 Vim 完全是反的。后者前期是一个竖直上升的难度，后来就平了。然而 haskell 看起来人畜无害，但是学了几节课后突然就进入了未知领域。笔者认为是有写一点东西的必要了。

多态、泛型

首先我们从最普通的函数开始。比如说

map :: (Int -> Int) -> [Int] -> [Int]

这是一个 map 函数，可以根据它的类型推断出它大概是接受一个修改 Int 类型值的函数与一个初始数组，然后它可以返回将这个函数应用于初始数组的每一个元素得到的最终数组。

这东西可以等价地理解为

map :: (Int -> Int) -> ([Int] -> [Int])

这时 map 的含义就变成了把一个 Int -> Int 的函数变换为一个 [Int] -> [Int] 类型的函数。

由此我们再做抽象，首先可以把底层类型多态化：

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

这样对于任意一个 a -> b 的函数我们都可以定义它对数组的 map 操作。

然后我们可以将外层类型泛型化：

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

这样对于任何一个类型构造符 f 和底层类型变换函数 a -> b，我们就都可以完成从 f a 到 f b 的变换。

听起来很简单，但是这个过程省略了很多东西：

  1. map' 中 [a] 是如何构造的？对于任意的类型 a 我们均可以构造关于此类型的列表。这是因为类型构造符 [] 提供了多态的支持。也就是说 fmap 中的 f 也应当是支持多态的。
  2. map' 的具体实现我们没有给出，但是显然这无法由编译器自动完成。也就是说 fmap 的实现也需要我们自己给出。

这样以来就出现了一些迷惑的地方。map' 尚且是有用的，因为它可以避免我们对不同类型的列表定义不同类型的 map。但是这个 fmap 就有点无用了。对不同的类型构造符，他们的构造方式各不相同，因此我们得各自声明一个针对该类型的 fmap 函数。这有什么意义呢？

类簇

为了解释上文提到的问题，我们需要理解 Haskell 中类簇的意义。Haskell 不是面向对象语言，因此它的 class 和通常意义的 class 有本质的区别。简单来说 Haskell 的 class 更接近于一种性质集合。具有公共性质的一些类型可以抽象出一个共同的 class。比如说

class Plusable a where
	(+) :: a -> a -> a

也就是说我们认为一个“可加”的类型应当具有一个加法运输符。class 中可以只声明运算符的类型，而其定义则在具体的类型中分别给出。

这样做的好处是可以将类型的性质划分到不同的 class 中，形成性质的依赖，这样就可以通过一些基本性质导出其他的性质。比如一个经典的例子

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

对于具有“可判等”性质的类型，我们可以定义它们的“不等于”运算符。

Functor

回到上文。对于具有 fmap 函数的类型，我们可以抽象出它们的 fmap 作为一个性质，得到一个 class：

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

Functor（函子）类型不仅是 “可 fmap” 的，而且具有一个导出的运算符 <$。从它的定义我们可以推测它的作用是将第二个参数 f b 的类型构造符 f 应用在第一个参数 a 上。也就是说如果只给我们一个 f b 类型的变量（而且我们不知道 f 怎么用），让我们把 a 变成 f a，我们可以直接利用 <$ 运算符完成同化。

除此以外我们可以将 fmap 理解为一个变种 $：

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

也就是说对于一个具有 Functor 性质的类型 f a，我们可以将任意 a -> b 的函数应用其上。

这时根据 Haskell 柯里化函数的特点，不难想到如下操作：

add :: a -> a -> a
add a b = a + b

那么问题来了：我们有两个 f a 类型的变量 fa 和 fb，我们想将他们利用 add 函数都加起来，怎么做？

fmap add 的类型为 f a -> f (a -> a)，也就说传入第一个参数后就会得到一个 f (a -> a) 类型的函数，怎么样把剩下的参数传进去？

直觉上你可能回想把 a -> a 从 f 中 “拿出来”。但是仔细一想就会发现这是拿不出来的。比如说当 f 是 [] 的时候。[a -> a] 代表的是一系列的函数，你无法取出一个函数代表其中所有。更本质地说，类型构造符不是可逆的。所以“拿出来”和“放进去”的过程是不能等价变换的。

Applicative

Functor 做不了的事，我们就让别人来做：

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

Applicative（可应用的）具有的性质是，首先它可以将一个任意类型 a 的变量同化为 f a，也称为纯化。

然后它可以将 f (a -> b) 类型的函数变量应用于 f a 和 f b。

这样也就解答了上文的疑惑。如果 f 也是 Applicative 的一个实例，那么我们可以

add <$> fa <*> fb

来实现函数的调用。当然我们可以直接使用 pure 将所有的计算全部放在 f 中进行：

pure add <*> fa <*> fb

当然为了不干碎直觉，我们要求你实现的 pure 和 <*> 满足一些性质（其实 Functor fmap 也有要求）。这样上述两种写法才能等价。

于是你会发现，add 的作用效果还取决于 <*> 的定义。而 pure 和 <$> 是有一定关系的，后者是 fmap 的一种快捷写法。

于是我们可以理解为，要把 add 函数“拿进” f 当中，需要经过 fmap 的过程，或者说 pure 的纯化。即便如此在应用 fmap add 的时候还是有 <*> 来时不时插一脚。因为 add 描述的是 a -> a -> a 的变换，而 f (a -> a -> a) 与 f a 的组合过程中还是需要一些粘合剂，来引导 f a 变成 a （如果能）再应用函数 a -> (a -> a) 然后变回 f (a -> a) 的过程。第二个参数的计算过程同理。

当然 Applicative 还提供了一些有用的函数

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

分别是取右和取左。

Monad

在 Applicative 的基础上我们引入 Monad：

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

Monad 定义了一个新的运算符 >>= 来描述对 m a 应用一个 a -> m b 的操作。然后把 pure 改写为了 return。

事实上 >>= 并不是任意定义的，它与 Applicative 的运算符 <*> 也得满足一些性质，但是这个性质比较不可读。我们可以从另一个推论来理解：

f <$> xs = fmap f xs  =  xs >>= return . f

也就是说 >>= 和 fmap 其实作用相似。要理解 >>= 的意义我们需要思考 a -> m b 与 a -> b 的区别。

不难发现，a -> m b 的返回值是被包裹在一个 Monad 的类型构造符中，这意味着函数的返回值将不再那么确切，因为我们知道所有关于底层类型的函数如果要放在 Applicative 的类型构造符中应用的话，势必会用到 fmap 和 <*>，这两者将会在你提供的函数的基础上做进一步的包装和变换。

但是为什么我们需要一个返回值不那么确切的函数？要对 m b 类型做变换的成本显然比 b 更高。

这是因为很多计算方式并不具备非常好的函数式编程的特点，如果要将返回值清楚地写出来的话，将会有许多无用的信息（比如，返回值可能是一个巨大的元组）。而且这会增加我们理解它的成本。有了 Monad，相当于我们只需要提供一个 a -> m b 的函数。从一个确切的 a 类型变换到 m b 我们是会的，因为 Monad 会提供 return，Applicative 也有 pure 函数可以使用。其他的部分（如何调用 a -> m b 的函数）则交给 <$> 和 <*> 完成。它的返回值究竟是不是确切的那个数已经不重要了。因为我们所有要做的事都写成了一个 a -> m b 的函数。

换言之，不要去向怎么把 b 从 m b 中取出来（因为 Monad 会帮我们做）。不妨直接写我们要把取出来的 b 做怎样的变换。

当然，Monad 也提供了一些其他的运算符来帮助我们变换：

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

这个操作相当于忽略前一个 Monad 的值，取后一个 Monad 的值。

另外，Haskell 为 Monad 设计了专门的语法糖，也就是 do：

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = 
	eval x >>= (\n -> 
	(eval y >>= (\m -> 
	safediv n m)))
-- 等价于
eval' :: Expr -> Maybe Int
eval' (Val n) = Just n
eval' (Div x y) = 
	do  n <- eval x
		m <- eval y
		safediv n m

<- 可以理解为把上一个 Monad 的返回值取出来继续用。当然如果两个普通的 Monad 在 do 中相邻的话连接符就是 >>。

另外，每一个 a -> m b 都可以被视作一个状态更新器。函数传入的 a 指代上一个状态，而返回的 m b 显然是下一个状态。

但是在这里还得扯几句。也许目前咱们已经对 Maybe a 这种 Monad 比较懂了，但是对于 Monad 到底是怎么做到辅助状态转移，将纯函数包装成“有状态的函数”，可能还是不太能上手。

为此我们需要思考 Haskell 状态保存的本质——通过函数传参实现。也就是说根本就没有全局变量，只不过是函数多加了一万个参数。

因此我们将 m a 的类型理解为 state -> (a, state)。那么 a -> m b 本质上是要求你根据捕获的 a 类型的值来返回一个 state 修改器，这个修改器还得顺便将 a 转换为 b 类型。

这个设计的妙处在于，你只需要写出 state 将会发生什么样的变化，而不需要关系 state 怎么被捕获的，和上文的地方也有相似之处。

运算律探究

接下来我们来分析一下 Functor、Applicative、Monad 各自满足怎样的运算律。这可以更好地帮助我们了解和阅读相关代码。

对于 Functor，它最基本的运算符是fmap，也就是 <$>，首先它是有（左）单位元的：

id :: a -> a
id a = a
-- identity law
id <$> a == a

另外它有复合律：

-- composition law
(f . g) <$> a == f <$> (g <$> a)
-- or
fmap (f . g) == fmap f . fmap g

不过阅读 link 可以知道，在 Haskell 中只要 fmap 的单位元性质成立，那么复合律自动成立。

Applicative 的运算律会更有意思。首先 <*> 有（左）单位元：

-- identity law
pure id <*> a == a

它也有复合律，不过这里的复合不再是 .，得用 pure (.)：

-- composition law
pure (.) <*> u <*> v <*> w == u <*> (v <*> w)
-- or
(.) <$> u <*> v <*> w == u <*> (v <*> w)

关于 pure 函数它还有同构律：

-- homomorphism law
pure f <*> pure x == pure (f x)

也就是说先纯化再应用等价于先应用再纯化。接下来是交换律：

-- interchange law
u <*> pure y = pure ($ y) <*> u
-- or
(<*> pure y) u = (<*> u) (pure ($ y))

也就是说先给你一个函数再告诉你传入的参数等价于先给你参数再告诉你应用到的那个函数。

Monad 的运算律就比较抽象了。为此我们先引入 Monad 复合运算：

-- The monad-composition operator
-- defined in Control.Monad
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

这样我们就可以发现 return 是它的单位元：

-- identity law
return >=> h == h
h >=> return == h

同时 >=> 具有结合律：

-- associativity law
(a >=> b) >=> c == a >=> (b >=> c)