# 函子专题

本专题主要讲解范畴论中`Functor`、`Applicative`、`Monad`三种函子对应的类型类，但我们尽量避免涉及的范畴相关的内容，而是以工程的视角将其视为特殊的类型类进行讲解，对于更深入有关范畴的内容，可参考后续[Haskell范畴论专题](#)。

## 函子类型类 `Functor` 

`Functor`类型类定义如下：

```hs
class Functor (f :: * -> *) where 
    fmap :: (a -> b) -> f a -> f b
    (<$) :: a -> f b -> f a
    {-# MINIMAL fmap #-}
```

`Functor`类型类最小实现是`fmap`函数。此前，我们已经学习过`map`函数，该函数类型签名为`(a -> b) -> [a] -> [b]`,其将函数作用在列表中的每一个元素，并使用函数作用的结果作为新列表。

细心的读者会发现`fmap`函数的类型签名与`map`函数非常相似，实际上，当我们将`fmap`函数类型中的`f`实例化为`[]`，该函数也就变称了`map`函数。

```bash
Prelude> f = fmap :: (a -> b) -> [a] -> [b]
Prelude> f (+1) [1,2,3,4]
[2,3,4,5]
```

`Functor`类型类将`map`函数抽象出来，使其能够处理更多其他的容器对象。

例如，`Maybe`类型已经内置了`Functor`类型类的实例，因此我们可以对其使用`fmap`函数：

```bash
Prelude> fmap (+1) (Just 1)
Just 2
Prelude> fmap (:[]) (Just 'a')
Just "a"
Prelude> fmap (++" world") (Just "hello")
Just "hello world"
Prelude> fmap id Nothing
Nothing
```

或者我们可以定义其他容器对象，并声明`Functor`实例,例如下面的二叉树：

```hs
-- code'1.hs
data Tree a = 
  Empty
  | Node a (Tree a) (Tree a) deriving (Show)

instance Functor Tree where
  fmap f Empty = Empty
  fmap f (Node a lchild rchild) = Node (f a) (fmap f lchild) (fmap f rchild)
```

该二叉树的定义有两种情形，空二叉树或者由结点和左右子树构成的树。通过声明二叉树的`Functor`实例，我们就可以对二叉树中的每个元素同时作用一个映射，使其更容易地生成新的二叉树：

```bash
Prelude> :load code'1.hs
Prelude> tree = Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty)
Prelude> fmap (+1) tree
Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty)
```

> 提示： 或者我们也可以使用DeriveFunctor扩展，自动派生`Functor`实例

为了使用方面，Haskell还提供了一个与`fmap`功能完全相同的运算符`<$>`,该运算符为左结合的中缀运算符，优先级为4。

```hs
infixl 4 <$>
```

除了`fmap`函数外，`Functor`类型类的另一个函数`<$`可以用`fmap`表示出来。

```hs
(<$) = fmap . const
```

该函数将第二个参数中容器中的每个元素都替换为第一个参数。

```bash
Prelude> 1 <$ Just 2
Just 1
Prelude> 1 <$ [1,2,3,4]
[1,1,1,1]
Prelude> 'a' <$ tree
Node 'a' (Node 'a' Empty Empty) (Node 'a' Empty Empty)
Prelude> (fmap . const) 'a' tree
Node 'a' (Node 'a' Empty Empty) (Node 'a' Empty Empty)
```

### 函子律

函子必须满足函子律：

- `fmap id = id`

- `fmap (f . g) = fmap f . fmap g`

虽然我们可以为特定类型声明`Functor`实例，但这并不能保证这个类型确实是函子，因此开发者必须保证声明的实例满足函子律。

以上面我们自行定义的`Tree`类型为例，我们来证明其保证了函子律：

```hs
-- fmap id = id 

fmap id Empty = Empty = id Empty 

fmap id (Node a lchild rchild) 
= Node (id a) (fmap id lchild) (fmap id rchild)
= Node a (fmap id lchild) (fmap id rchild) -- 归纳假设
= Node a lchild rchild
= id (Node a lchild rchild)
-- fmap (f . g) = fmap f . fmap g

fmap (f . g) Empty 
= Empty 
= fmap f Empty
= fmap f (fmap g Empty)
= (fmap f . fmap g) Empty

fmap (f . g) (Node a lchild rchild)
= Node ((f . g) a) (fmap (f . g) lchild) (fmap (f . g) rchild)
= Node (f (g a)) ((fmap f . fmap g) lchild) ((fmap f . fmap g) rchild) -- 归纳假设
= fmap f (Node (g a) (fmap g lchild) (fmap g rchild))
= fmap f (fmap g (Node a lchild rchild))
= (fmap f . fmap g) (Node a lchld rchild)
```

> 提示：上述证明过程中使用到了结构归纳法，对此概念陌生的读者可以自行搜索了解

## 应用函子类型类 `Applicative`

应用函子是特殊的函子，因此`Applicative`类型类受到`Functor`的约束，其定义如下：

```hs
class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  liftA2 :: (a -> b -> c) -> f a -> f b -> f c 
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a
  {-# MINIMAL pure, ((<*>) | liftA2) #-}
```

最小实现为`pure`函数，以及`(<*>)`函数和`liftA2`中的任意一个。

> 提示：这里使用的定义位于`Control.Applicative`，在GHCi中默认使用`GHC.Base`中的定义，这些定义会有微小的差异

`pure`函数将一个值放到一个容器中：

```bash
Prelude> pure 1 :: [Int]
[1]
Prelude> pure 1 :: Maybe Int 
Just 1
```

`<*>`函数接受一个带有`a -> b`类型函数的容器，以及带有`a`类型元素的容器，在保持容器结构的情况下，依次将第一个容器中的函数作用到第二个容器中的元素，最终生成新的容器。

```bash
Prelude> Just (+1) <*> Just 1
Just 2
Prelude> Just id <*> Nothing
Nothing
Prelude> Nothing <*> Just 1
Nothing
Prelude> [(+1),(+2)] <*> [1,2]
[2,3,3,4]
Prelude> [(+1),(+2)] <*> [1,2,3]
[2,3,4,3,4,5]
Prelude> [(+1),(+2)] <*> []
[]
```

> 补充： 读者可能会疑惑为什么列表使用`<*>`的效果得到的是笛卡尔积, 而不是对应位置函数应用在对应位置的元素上（这里我们借用来源于Python的概念“广播”），这可能与Haskell的开发历史有关；实际上我们可以用列表的同构类型（指newtype声明）ZipList，该数据类型位于`Control.Applicative`中，并在应用函子实例中实现了广播操作。我们提供了一个自定义的版本供读者参考：
> ```hs
> -- code'1.hs
>
> newtype L a = L [a] 
>    deriving newtype (Show,Functor,Semigroup,Monoid)
>
>instance Applicative L where
>  pure x = L (repeat x)
>  (L []) <*> _ = mempty
>  _ <*> (L []) = mempty
>  (L (f:fs)) <*> (L (x:xs)) = L [f x] <> (L fs <*> L xs)
> ```

`liftA2`函数接受一个类型为`a -> b -> c`的二元函数，以及两个分别装有类型为`a`和`b`的容器，在保持容器结构的情况下，该函数将二元函数依次作用与后两个容器中的元素，生成新的容器。

`liftA2`与`<*>`可以互相定义，这也是最小实现中只要二选一即可。

```hs
-- Applicative f =>
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2 f t1 t2 =  (pure f) <*> t1 <*> t2  --fmap f t1 <*> t2

-- Applicative f => 
(<*>) :: f (a -> b) -> f a -> f b
tf <*> t = liftA2 (\ f a -> f a) tf t
```

下面给出几个示例：

```bash
Prelude> Just (+) <*> Just 1 <*> Just 2
Just 3
Prelude> liftA2 (+) (Just 1) (Just 2)
Just 3
```

`<*`和`*>`功能比较类似，它们接受两个容器，并将其中一个容器中的元素按次序替换为另一个容器中的元素。它们可以通过`<*>`或者`liftA2`函数表示出来。

```hs
-- Applicative f => 
(<*) :: f a -> f b -> f b
fa <* fb =  pure const <*> fa <*> fb
  -- liftA2 const fa fb
  -- fmap const fa <*> fb

(*>) :: f a -> f b -> f a 
fa *> fb = pure (flip const) <*> fa <*> fb
  -- liftA2 (flip const) fa fb 
  -- fmap (flip const) fa fb
```


最后给出有关二叉树的应用函子实例的声明：

```hs
-- code'1.hs

instance Applicative Tree where 
  pure x = let tree = Node x tree tree 
            in tree 
  Empty <*> _ = Empty 
  _ <*> Empty = Empty 
  Node f flchild frchild <*> Node x lchild rchild = Node (f x) (flchild <*> lchild) (frchild <*> rchild) 
```

> 提示： `pure`的定义中出现了一个循环定义的树，这似乎很奇怪，这是因为需要其需要满足应用函子律（如下）

### 应用函子律

类似的，应用函子必须满足应用函子律，这些条件必须由开发者自行保证。

- 同一律： `pure id <*> v = v`
- 同态律： `pure f <*> pure x = pure (f x)`
- 互换律： `u <*> pure y = pure ($ y) <*> u`
- 组合律： `pure (.) <*> u <*> v <*> w = u <*> (v <*> w)`

> 提示：在互换律中首次出现运算符`$`，该运算符类型为`(a -> b) -> a -> b`,结合性与优先级为`infixr 0 $`。该运算符是一个语法糖，可以用于去除过多括号，如`f (...)`可以写为`f $ ...`

下面证明二叉树满足应用函子律：

```hs
-- pure id <*> v = v 

pure id <*> Empty 
= Empty 

pure id <*> (Node x lchild rchild)
= (Node id tree tree) <*> (Node x lchild rchild) -- tree = Node id tree tree = pure id
= Node (id x) (tree <*> lchild) (tree <*> rchild)
= Node x (tree <*> lchild) (tree <*> rchild) 
= Node x (pure id <*> lchild) (pure id <*> rchild)
= Node x lchild rchild

-- pure f <*> pure x = pure (f x)
pure f <*> pure x
= (Node f treef treef) <*> (Node x treex treex) 
  -- treef = Node f treef treef = pure f
  -- treex = Node x treex treex = pure x
= Node (f x) (treef <*> treex) (treef <*> treex)
= Node (f x) (pure f <*> pure x) (pure f <*> pure x)
= Node (f x) (Node (f x) ...) (Node (f x) ...)

pure (f x) 
= Node (f x) treefx treefx 
  -- treefx = Node (f x) treefx treefx = pure (f x)
= Node (f x) (pure (f x)) (pure (f x))
= Node (f x) (Node (f x) ...) (Node (f x) ...)

-- u <*> pure y = pure ($ y) <*> u
当 u = Empty 时：

u <*> pure y 
= Empty <*> pure y
= Empty 
= pure ($ y) <*> Empty = pure ($ y) <*> u

当 u = Node f lchild rchild 时,

u <*> pure y 
= Node f lchild rchild <*> Node y tree tree 
  -- tree = Node y tree tree = pure y 
= Node (f y) (lchild <*> tree) (rchild <*> tree)
= Node (f y) (lchild <*> pure y) (rchild <*> pure y)
= Node (($ y) f) (pure ($ y) <*> lchild) (pure ($ y) <*> rchild) -- 归纳假设
= pure ($ y) <*> Node f lchild rchild 
= pure ($ y) <*> u

-- pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
当 u, v, w 任一为 Empty 时，等式均成立



令 u = Node f lchild rchild , 
v = Node g lchild' rchild', 
w = Node x lchild'' rchild''

pure (.) <*> u <*> v <*> w
= Node (.) tree tree <*> Node f lchild rchild <*> v <*> w
  -- tree = Node (.) tree tree = pure (.)
= Node (f .) (tree <*> lchild) (tree <*> rchild) <*> v <*> w
= Node (f .) (tree <*> lchild) (tree <*> rchild) <*> Node g lchild' rchild' <*> Node x lchild'' rchild''
= Node (f . g) (tree <*> lchild <*> lchild') (tree <*> rchild <*> rchild') <*> Node x lchild'' rchild''
= Node ((f . g) x) (tree <*> lchild <*> lchild' <*> lchild'') (tree <*> rchild <*> rchild' <*> rchild'')
= Node (f (g x)) (pure (.) <*> lchild <*> lchild' <*> lchild'')
(pure (.) <*> rchild <*> rchild' <*> rchild'')
= Node (f (g x)) (lchild <*> (lchild' <*> lchild'')) (rchild <*> (rchild' <*> rchild'')) -- 归纳假设
= Node f lchild rchild <*> Node (g x) (lchild' <*> lchild'') (rchild' <*> rchild'')
= Node f lchild rchild <*> (Node g lchild' rchild' <*> Node x lchild'' rchild'')
= u <*> (v <*> w)
```

## 单子类型类 `Monad`

`Monad`类型类也是一种特殊的应用函子，这里只给出定义和一些例子，更多内容请移步[Monad专题](/haskell/专题/Monad专题)。

```hs
class Applicatve m => Monad (m :: * -> *) where 
  (>>=) :: m a -> (a -> m b) -> m b 
  (>>) :: m a -> m b -> m b 
  return :: a -> m a 
  fail :: String -> m a 
  {-# MINIMAL (>>=) #-}
```

`Monad`类型类的最小实现为`(>>=)`，它接受一个容器`m a`，以及一个类型为`a -> m b`的函数,并将第二个函数依次应用于第一个容器中的元素，最后生成新的容器。

```bash
Prelude> Nothing >>= \t -> Just (t + 1)
Nothing
Prelude> Just 1 >>= \t -> Just (t + 1)
Just 2
Prelude> [] >>= \t -> [t + 1]
[]
Prelude> [1,2,3,4] >>= \t -> [t + 1]
[2,3,4,5]
Prelude> [(+1),(+2),(+3),(+4)] >>= \f -> [f 1]
[2,3,4,5]
```

除了`(>>=)`外，`Monad`类型类还提供了`return`函数将一个数值`a`映射为包含该元素的容器，对应了`Applicative`中的`pure`函数；`(>>)`类似`(>>=)`，区别是`(>>)`并没有将第一个参数传入第二个参数中；最后`fail`用于计算错误时进行报错。

> 注意： 在新版本中，`fail`函数已经被移出Monad类型类中，而是移植到单独创建的MonadFail类型类；在新版本改进的提议中，`fail`的某些不恰当行为被进一步规范。读者可以对照两个函数的文档获得更全面的了解

```hs
-- Monad m => 
return :: a -> m a
return = pure 
-- Monad m =>
(>>) :: m a -> m b -> m b 
ma >> mb = ma >>= const mb
```

------------------------------------------

<p id="ref1">[1] Typeclassopedia. (2022, December 30). HaskellWiki, . Retrieved 07:43, April 19, 2024 from https://wiki.haskell.org/index.php?title=Typeclassopedia&oldid=65490.</p>