函子专题

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

函子类型类 `Functor`

Functor类型类定义如下：

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函数。

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

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

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

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实例,例如下面的二叉树：

-- 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实例，我们就可以对二叉树中的每个元素同时作用一个映射，使其更容易地生成新的二叉树：

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。

infixl 4 <$>

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

(<$) = fmap . const

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

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类型为例，我们来证明其保证了函子律：

-- 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的约束，其定义如下：

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函数将一个值放到一个容器中：

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

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

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中，并在应用函子实例中实现了广播操作。我们提供了一个自定义的版本供读者参考：
-- 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与<*>可以互相定义，这也是最小实现中只要二选一即可。

-- 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

下面给出几个示例：

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

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

-- 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

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

-- 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 $ ...

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

-- 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专题。

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的函数,并将第二个函数依次应用于第一个容器中的元素，最后生成新的容器。

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的某些不恰当行为被进一步规范。读者可以对照两个函数的文档获得更全面的了解

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

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

函子专题

函子类型类 Functor

函子律

应用函子类型类 Applicative

应用函子律

单子类型类 Monad

函子类型类 `Functor`

应用函子类型类 `Applicative`

单子类型类 `Monad`