[Haskell] Functor

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

其中f并不是一个具体类型，而是一个单参类型构造器（:k f = * -> *）。
类型f a的值称为functor value。
<u></u>fmap接受一个普通函数a -> b，返回一个functor value上的函数f a -> f b。

Functor Law
只是Functor类型类的实例，还不是一个数学意义上的Functor，需要满足以下定律。
（1）fmap id = id
（2）fmap (f . g) = fmap f . fmap g

Examples

（1）[]是Functor类型类的实例

instance Functor [] where
fmap = map

列表类型上的map就是fmap。

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

注：
不能写“instance Functor [a] where”而要写“[]” （:k [] = * -> *），因为Functor类型类的实例必须是一个单参类型构造器，而“[a]”是一个具体类型。

（2）Maybe是Functor类型类的实例

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

其中，Maybe类型的定义如下：

data Maybe a = Just a | Nothing

其中，fmap :: (a -> b) -> Maybe a -> Maybe b

（3）Tree是Functor类型类的实例

instance Functor Tree where
fmap f EmptyTree = EmptyTree
fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

其中，Tree类型的定义如下：

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

（4）Either a是Functor类型类的实例

<u></u>Either a b是一个具体类型，而Functor类型类的实例必须是单参类型构造器。
而Either是接受两个参数的类型构造器（:k Either = * -> * -> *），也不可以。
部分应用Either的一个参数类型，得到Either a，它是一个单参类型构造器了（:k Either a = * -> *）。

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

其中，Either类型的定义如下：

data Either a b = Left a | Right b

（5）(->) r是Functor类型类的实例

函数类型r -> a可以改写为：(->) r a，则“->”就是一个接受两个参数的类型构造器了（:k (->) = * -> * -> *）。
如果已提供一个类型参数，则“(->) r”就是单参类型构造器了（:k (-> r) = * -> *），可以作为Functor类型类的实例了。其中，(->) r = (r ->)

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

我们考虑一下fmap的类型是如何实例化的

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

而这正好是函数复合“.”的类型，所以fmap还可以定义为：

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

因此，fmap作用在两个函数上面，就相当于进行函数复合。

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

还可以有不同的写法：

fmap (* 3) (+ 100) 1
= (* 3) `fmap` (+ 100) $ 1
= (* 3) . (+ 100) $ 1