Functors, Applicative Functors 与 Monoids

Haskell 的一些特色，像是纯粹性，高端函数，algebraic data types，typeclasses，这些让我们可以从更高的角度来看到 polymorphism 这件事。不像 OOP 当中需要从庞大的型态阶层来思考。我们只需要看看手边的型态的行为，将他们跟适当地 typeclass 对应起来就可以了。像 Int 的行为跟很多东西很像。好比说他可以比较相不相等，可以从大到小排列，也可以将他们一一穷举出来。
Typeclass 的运用是很随意的。我们可以定义自己的数据型态，然后描述他可以怎样被操作，跟 typeclass 关联起来便定义了他的行为。由于 Haskell 强大的型态系统，这让我们只要读函数的型态宣告就可以知道很多信息。typeclass 可以定义得很抽象很 general。我们之前有看过 typeclass 定义了可以比较两个东西是否相等，或是定义了可以比较两个东西的大小。这些是既抽象但又描述简洁的行为，但我们不会认为他们有什么特别之处，因为我们时常碰到他们。最近我们看过了 functor，基本上他们是一群可以被 map over 的对象。这是其中一个例子能够抽象但又漂亮地描述行为。在这一章中，我们会详加阐述 functors，并会提到比较强一些的版本，也就是 applicative functors。我们也会提到 monoids。
温习 Functors
我们已经在之前的章节提到 functors。如果你还没读那个章节，也许你应该先去看看。或是你直接假装你已经读过了。
来快速复习一下：Functors 是可以被 map over 的对象，像是 lists，Maybe，trees 等等。在 Haskell 中我们是用 Functor 这个 typeclass 来描述他。这个 typeclass 只有一个 method，叫做 fmap，他的型态是 fmap :: (a -> b) -> f a -> f b。这型态说明了如果给我一个从 a 映到 b 的函数，以及一个装了 a 的盒子，我会回给你一个装了 b 的盒子。就好像用这个函数将每个元素都转成 b 一样
*给一点建议*。这盒子的比喻尝试让你抓到些 functors 是如何运作的感觉。在之后我们也会用相同的比喻来比喻 applicative functors 跟 monads。在多数情况下这种比喻是恰当的，但不要过度引申，有些 functors 是不适用这个比喻的。一个比较正确的形容是 functors 是一个计算语境（computational context）。这个语境可能是这个 computation 可能带有值，或是有可能会失败（像 ``Maybe`` 跟 ``Either a``），或是他可能有多个值（像 lists），等等。
如果一个 type constructor 要是 Functor 的 instance，那他的 kind 必须是 * -> *，这代表他必须刚好接受一个 type 当作 type parameter。像是 Maybe 可以是 Functor 的一个 instance，因为他接受一个 type parameter，来做成像是 Maybe Int，或是 Maybe String。如果一个 type constructor 接受两个参数，像是 Either，我们必须给他两个 type parameter。所以我们不能这样写：instance Functor Either where，但我们可以写 instance Functor (Either a) where，如果我们把 fmap 限缩成只是 Either a 的，那他的型态就是 fmap :: (b -> c) -> Either a b -> Either a c。就像你看到的，Either a 的是固定的一部分，因为 Either a 只恰好接受一个 type parameter，但 Either 则要接受两个 type parameters。这样 fmap 的型态变成 fmap :: (b -> c) -> Either b -> Either c，这不太合理。
我们知道有许多态态都是 Functor 的 instance，像是 []，Maybe，Either a 以及我们自己写的 Tree。我们也看到了如何用一个函数 map 他们。在这一章节，我们再多举两个例子，也就是 IO 跟 (->) r。
如果一个值的型态是 IO String，他代表的是一个会被计算成 String 结果的 I/O action。我们可以用 do syntax 来把结果绑定到某个名称。我们之前把 I/O action 比喻做长了脚的盒子，会到真实世界帮我们取一些值回来。我们可以查看他们取了什么值，但一旦看过，我们必须要把值放回盒子中。用这个比喻，IO 的行为就像是一个 functor。
我们来看看 IO 是怎么样的一个 Functor instance。当我们 fmap 用一个 function 来 map over I/O action 时，我们会想要拿回一个装着已经用 function 映射过值的 I/O action。
instance Functor IO where
    fmap f action = do
        result <- action
        return (f result)
对一个 I/O action 做 map over 动作的结果仍会是一个 I/O action，所以我们才用 do syntax 来把两个 I/O action 黏成一个。在 fmap 的实作中，我们先执行了原本传进的 I/O action，并把结果绑定成 result。然后我们写了 return (f result)。return 就如你所知道的，是一个只会回传包了你传给他东西的 I/O action。还有一个 do block 的回传值一定是他最后一个 I/O action 的回传值。这也是为什么我们需要 return。其实他只是回传包了 f result 的 I/O action。
我们可以再多实验一下来找到些感觉。来看看这段 code：
main = do line <- getLine   
        let line' = reverse line  
        putStrLn $ "You said " ++ line' ++ " backwards!"  
        putStrLn $ "Yes, you really said" ++ line' ++ " backwards!"
这程序要求用户输入一行文本，然后印出一行反过来的。 我们可以用 fmap 来改写：
main = do line <- fmap reverse getLine  
            putStrLn $ "You said " ++ line ++ " backwards!"  
            putStrLn $ "Yes, you really said" ++ line ++ " backwards!"
就像我们用 fmap reverse 来 map over Just "blah" 会得到 Just "halb"，我们也可以 fmap reverse 来 map over getLine。getLine 是一个 I/O action，他的 type 是 IO String，而用 reverse 来 map over 他会回传一个取回一个字串并 reverse 他的 I/O action。就像我们 apply 一个 function 到一个 Maybe 一样，我们也可以 apply 一个 function 到一个 IO，只是这个 IO 会跑去外面拿回某些值。然后我们把结果用 <- 绑定到某个名称，而这个名称绑定的值是已经 reverse 过了。
而 fmap (++"!") getLine 这个 I/O action 表现得就像 getLine，只是他的结果多了一个 "!" 在最后。
如果我们限缩 fmap 到 IO 型态上，那 fmap 的型态是 fmap :: (a -> b) -> IO a -> IO b。fmap 接受一个函数跟一个 I/O action，并回传一个 I/O action 包含了已经 apply 过 function 的结果。
如果你曾经注意到你想要将一个 I/O action 绑定到一个名称上，只是为了要 apply 一个 function。你可以考虑使用 fmap，那会更漂亮地表达这件事。或者你想要对 functor 中的数据做 transformation，你可以先将你要用的 function 写在 top level，或是把他作成一个 lambda function，甚至用 function composition。
import Data.Char  
import Data.List  
​
main = do line <- fmap (intersperse '-' . reverse . map toUpper) getLine  
          putStrLn line
$ runhaskell fmapping_io.hs  
hello there  
E-R-E-H-T- -O-L-L-E-H
正如你想的，intersperse '-' . reverse . map toUpper 合成了一个 function，他接受一个字串，将他转成大写，然后反过来，再用 intersperse '-' 安插'-'。他是比较漂亮版本的 (\xs -> intersperse '-' (reverse (map toUpper xs)))。
另一个 Functor 的案例是 (->) r，只是我们先前没有注意到。你可能会困惑到底 (->) r 究竟代表什么？一个 r -> a 的型态可以写成 (->) r a，就像是 2 + 3 可以写成 (+) 2 3 一样。我们可以从一个不同的角度来看待 (->) r a，他其实只是一个接受两个参数的 type constructor，好比 Either。但记住我们说过 Functor 只能接受一个 type constructor。这也是为什么 (->) 不是 Functor 的一个 instance，但 (->) r 则是。如果程序的语法允许的话，你也可以将 (->) r 写成 (r ->)。就如 (2+) 代表的其实是 (+) 2。至于细节是如何呢？我们可以看看 Control.Monad.Instances。
我们通常说一个接受任何东西以及回传随便一个东西的函数型态是 ``a -> b``。``r -> a`` 是同样意思，只是把符号代换了一下。
instance Functor ((->) r) where  
    fmap f g = (\x -> f (g x))
如果语法允许的话，他可以被写成
instance Functor (r ->) where  
    fmap f g = (\x -> f (g x))
但其实是不允许的，所以我们必须写成第一种的样子。
首先我们来看看 fmap 的型态。他的型态是 fmap :: (a -> b) -> f a -> f b。我们把所有的 f 在心里代换成 (->) r。则 fmap 的型态就变成 fmap :: (a -> b) -> ((->) r a) -> ((->) r b)。接着我们把 (->) r a 跟 (->) r b 换成 r -> a 跟 r -> b。则我们得到 fmap :: (a -> b) -> (r -> a) -> (r -> b)。
从上面的结果看到将一个 function map over 一个 function 会得到另一个 function，就如 map over 一个 function 到 Maybe 会得到一个 Maybe，而 map over 一个 function 到一个 list 会得到一个 list。而 fmap :: (a -> b) -> (r -> a) -> (r -> b) 告诉我们什么？他接受一个从 a 到 b 的 function，跟一个从 r 到 a 的 function，并回传一个从 r 到 b 的 function。这根本就是 function composition。把 r -> a 的输出接到 a -> b 的输入，的确是 function composition 在做的事。如果你再仔细看看 instance 的定义，会发现真的就是一个 function composition。
instance Functor ((->) r) where  
    fmap = (.)
这很明显就是把 fmap 当 composition 在用。可以用 :m + Control.Monad.Instances 把模块装载进来，并做一些尝试。
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  
ghci> fmap (show . (*3)) (*100) 1  
"300"
我们调用 fmap 的方式是 infix 的方式，这跟 . 很像。在第二行，我们把 (*3) map over 到 (+100) 上，这会回传一个先把输入值 (+100) 再 (*3) 的 function，我们再用 1 去调用他。
到这边为止盒子的比喻还适用吗？如果你硬是要解释的话还是解释得通。当我们将 fmap (+3) map over Just 3 的时候，对于 Maybe 我们很容易把他想成是装了值的盒子，我们只是对盒子里面的值 (+3)。但对于 fmap (*3) (+100) 呢？你可以把 (+100) 想成是一个装了值的盒子。有点像把 I/O action 想成长了脚的盒子一样。对 (+100) 使用 fmap (*3) 会产生另一个表现得像 (+100) 的 function。只是在算出值之前，会再多计算 (*3)。这样我们可以看出来 fmap 表现得就像 . 一样。
fmap 等同于 function composition 这件事对我们来说并不是很实用，但至少是一个有趣的观点。这也让我们打开视野，看到盒子的比喻不是那么恰当，functors 其实比较像 computation。function 被 map over 到一个 computation 会产生经由那个 function 映射过后的 computation。
在我们继续看 fmap 该遵守的规则之前，我们再看一次 fmap 的型态，他是 fmap :: (a -> b) -> f a -> f b。很明显我们是在讨论 Functor，所以为了简洁，我们就不写 (Functor f) => 的部份。当我们在学 curry 的时候，我们说过 Haskell 的 function 实际上只接受一个参数。一个型态是 a -> b -> c 的函数实际上是接受 a 然后回传 b -> c，而 b -> c 实际上接受一个 b 然后回传一个 c。如果我们用比较少的参数调用一个函数，他就会回传一个函数需要接受剩下的参数。所以 a -> b -> c 可以写成 a -> (b -> c)。这样 curry 可以明显一些。
同样的，我们可以不要把 fmap 想成是一个接受 function 跟 functor 并回传一个 function 的 function。而是想成一个接受 function 并回传一个新的 function 的 function，回传的 function 接受一个 functor 并回传一个 functor。他接受 a -> b 并回传 f a -> f b。这动作叫做 lifting。我们用 GHCI 的 :t 来做的实验。
ghci> :t fmap (*2)  
fmap (*2) :: (Num a, Functor f) => f a -> f a  
ghci> :t fmap (replicate 3)  
fmap (replicate 3) :: (Functor f) => f a -> f [a]
fmap (*2) 接受一个 functor f，并回传一个基于数字的 functor。那个 functor 可以是 list，可以是 Maybe，可以是 Either String。fmap (replicate 3) 可以接受一个基于任何型态的 functor，并回传一个基于 list 的 functor。
当我们提到 functor over numbers 的时候，你可以想像他是一个 functor 包含有许多数字在里面。前面一种说法其实比较正确，但后面一种说法比较容易让人理解。
这样的观察在我们只有绑定一个部份套用的函数，像是 fmap (++"!")，的时候会显得更清楚，
你可以把 fmap 想做是一个函数，他接受另一个函数跟一个 functor，然后把函数对 functor 每一个元素做映射，或你可以想做他是一个函数，他接受一个函数并把他 lift 到可以在 functors 上面操作。两种想法都是正确的，而且在 Haskell 中是等价。
fmap (replicate 3) :: (Functor f) => f a -> f [a] 这样的型态代表这个函数可以运作在任何 functor 上。至于确切的行为则要看究竟我们操作的是什么样的 functor。如果我们是用 fmap (replicate 3) 对一个 list 操作，那我们会选择 fmap 针对 list 的实作，也就是只是一个 map。如果我们是碰到 Maybe a。那他在碰到 Just 型态的时候，会对里面的值套用 replicate 3。而碰到 Nothing 的时候就回传 Nothing。
ghci> fmap (replicate 3) [1,2,3,4]  
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]  
ghci> fmap (replicate 3) (Just 4)  
Just [4,4,4]  
ghci> fmap (replicate 3) (Right "blah")  
Right ["blah","blah","blah"]  
ghci> fmap (replicate 3) Nothing  
Nothing  
ghci> fmap (replicate 3) (Left "foo")  
Left "foo"
接下来我们来看看 functor laws。一个东西要成为 functor，必须要遵守某些定律。不管任何一个 functor 都被要求具有某些性质。他们必须是能被 map over 的。对他们调用 fmap 应该是要用一个函数 map 每一个元素，不多做任何事情。这些行为都被 functor laws 所描述。对于 Functor 的 instance 来说，总共两条定律应该被遵守。不过他们不会在 Haskell 中自动被检查，所以你必须自己确认这些条件。
functor law 的第一条说明，如果我们对 functor 做 map id，那得到的新的 functor 应该要跟原来的一样。如果写得正式一点，他代表 fmap id = id。基本上他就是说对 functor 调用 fmap id，应该等同于对 functor 调用 id 一样。毕竟 id 只是 identity function，他只会把参数照原样丢出。他也可以被写成 \x -> x。如果我们对 functor 的概念就是可以被 map over 的对象，那 fmap id = id 的性就显而易见。
我们来看看这个定律的几个案例：
ghci> fmap id (Just 3)  
Just 3  
ghci> id (Just 3)  
Just 3  
ghci> fmap id [1..5]  
[1,2,3,4,5]  
ghci> id [1..5]  
[1,2,3,4,5]  
ghci> fmap id []  
[]  
ghci> fmap id Nothing  
Nothing
如果我们看看 Maybe 的 fmap 的实作，我们不难发现第一定律为何被遵守。
instance Functor Maybe where  
    fmap f (Just x) = Just (f x)  
    fmap f Nothing = Nothing
我们可以想像在 f 的位置摆上 id。我们看到 fmap id 拿到 Just x 的时候，结果只不过是 Just (id x)，而 id 有只回传他拿到的东西，所以可以知道 Just (id x) 等价于 Just x。所以说我们可以知道对 Maybe 中的 Just 用 id 去做 map over 的动作，会拿回一样的值。
而将 id map over Nothing 会拿回 Nothing 并不稀奇。所以从这两个 fmap 的实作，我们可以看到的确 fmap id = id 有被遵守。
第二定律描述说先将两个函数合成并将结果 map over 一个 functor 的结果，应该跟先将第一个函数 map over 一个 functor，再将第二个函数 map over 那个 functor 的结果是一样的。正式地写下来的话就是 fmap (f . g) = fmap f . fmap g。或是用另外一种写法，对于任何一个 functor F，下面这个式子应该要被遵守：fmap (f . g) F = fmap f (fmap g F)。
如果我们能够证明某个型别遵守两个定律，那我们就可以保证他跟其他 functor 对于映射方面都拥有相同的性质。我们知道如果对他用 fmap，我们知道不会有除了 mapping 以外的事会发生，而他就仅仅会表现成某个可以被 map over 的东西。也就是一个 functor。你可以再仔细查看 fmap 对于某些型别的实作来了解第二定律。正如我们先前对 Maybe 查看第一定律一般。
如果你需要的话，我们能在这边演练一下 Maybe 是如何遵守第二定律的。首先 fmap (f . g) 来 map over Nothing 的话，我们会得到 Nothing。因为用任何函数来 fmap Nothing 的话都会回传 Nothing。如果我们 fmap f (fmap g Nothing)，我们会得到 Nothing。可以看到当面对 Nothing 的时候，Maybe 很显然是遵守第二定律的。 那对于 Just something 呢？如果我们使用 fmap (f . g) (Just x) 的话，从实作的代码中我可以看到 Just ((f . g ) x)，也就是 Just (f (g x))。如果我们使用 fmap f (fmap g (Just x)) 的话我们可以从实作知道 fmap g (Just x) 会是 Just (g x)。fmap f (fmap g (Just x)) 跟 fmap f (Just (g x)) 相等。而从实作上这又会相等于 Just (f (g x))。
如果你不太理解这边的说明，别担心。只要确定你了解什么是函数合成就好。在多数的情况下你可以直觉地对应到这些型别表现得就像 containers 或函数一样。或是也可以换种方法，只要多尝试对型别中不同的值做操作你就可以看看型别是否有遵守定律。
我们来看一些经典的例子。这些型别建构子虽然是 Functor 的 instance，但实际上他们并不是 functor，因为他们并不遵守这些定律。我们来看看其中一个型别。
data CMaybe a = CNothing | CJust Int a deriving (Show)
C 这边代表的是计数器。他是一种看起来像是 Maybe a 的型别，只差在 Just 包含了两个 field 而不是一个。在 CJust 中的第一个 field 是 Int，他是扮演计数器用的。而第二个 field 则为型别 a，他是从型别参数来的，而他确切的型别当然会依据我们选定的 CMaybe a 而定。我们来对他作些操作来获得些操作上的直觉吧。
ghci> CNothing  
CNothing  
ghci> CJust 0 "haha"  
CJust 0 "haha"  
ghci> :t CNothing  
CNothing :: CMaybe a  
ghci> :t CJust 0 "haha"  
CJust 0 "haha" :: CMaybe [Char]  
ghci> CJust 100 [1,2,3]  
CJust 100 [1,2,3]
如果我们使用 CNothing，就代表不含有 field。如果我们用的是 CJust，那第一个 field 是整数，而第二个 field 可以为任何型别。我们来定义一个 Functor 的 instance，这样每次我们使用 fmap 的时候，函数会被套用在第二个 field，而第一个 field 会被加一。
instance Functor CMaybe where  
    fmap f CNothing = CNothing  
    fmap f (CJust counter x) = CJust (counter+1) (f x)
这种定义方式有点像是 Maybe 的定义方式，只差在当我们使用 fmap 的时候，如果碰到的不是空值，那我们不只会套用函数，还会把计数器加一。我们可以来看一些范例操作。
ghci> fmap (++"ha") (CJust 0 "ho")  
CJust 1 "hoha"  
ghci> fmap (++"he") (fmap (++"ha") (CJust 0 "ho"))  
CJust 2 "hohahe"  
ghci> fmap (++"blah") CNothing  
CNothing
这些会遵守 functor laws 吗？要知道有不遵守的情形，只要找到一个反例就好了。
ghci> fmap id (CJust 0 "haha")  
CJust 1 "haha"  
ghci> id (CJust 0 "haha")  
CJust 0 "haha"
我们知道 functor law 的第一定律描述当我们用 id 来 map over 一个 functor 的时候，他的结果应该跟只对 functor 调用 id 的结果一样。但我们可以看到这个例子中，这对于 CMaybe 并不遵守。尽管他的确是 Functor typeclass 的一个 instace。但他并不遵守 functor law 因此不是一个 functor。如果有人使用我们的 CMaybe 型别，把他当作 functor 用，那他就会期待 functor laws 会被遵守。但 CMaybe 并没办法满足，便会造成错误的程序。当我们使用一个 functor 的时候，函数合成跟 map over 的先后顺序不应该有影响。但对于 CMaybe 他是有影响的，因为他纪录了被 map over 的次数。如果我们希望 CMaybe 遵守 functor law，我们必须要让 Int 字段在做 fmap 的时候维持不变。
乍看之下 functor laws 看起来不是很必要，也容易让人搞不懂，但我们知道如果一个型别遵守 functor laws，那我们就能对他作些基本的假设。如果遵守了 functor laws，我们知道对他做 fmap 不会做多余的事情，只是用一个函数做映射而已。这让写出来的代码足够抽象也容易扩展。因为我们可以用定律来推论型别的行为。
所有在标准函式库中的 Functor 的 instance 都遵守这些定律，但你可以自己检查一遍。下一次你定义一个型别为 Functor 的 instance 的时候，花点时间确认他确实遵守 functor laws。一旦你操作过足够多的 functors 时，你就会获得直觉，知道他们会有什么样的性质跟行为。而且 functor laws 也会觉得显而易见。但就算没有这些直觉，你仍然可以一行一行地来找看看有没有反例让这些定律失效。
我们可以把 functor 看作输出具有 context 的值。例如说 Just 3 就是输出 3，但他又带有一个可能没有值的 context。[1,2,3] 输出三个值，1,2 跟 3，同时也带有可能有多个值或没有值的 context。(+3) 则会带有一个依赖于参数的 context。
如果你把 functor 想做是输出值这件事，那你可以把 map over 一个 functor 这件事想成在 functor 输出的后面再多加一层转换。当我们做 fmap (+3) [1,2,3] 的时候，我们是把 (+3) 接到 [1,2,3] 后面，所以当我们查看任何一个 list 的输出的时候，(+3) 也会被套用在上面。另一个例子是对函数做 map over。当我们做 fmap (+3) (*3)，我们是把 (+3) 这个转换套用在 (*3) 后面。这样想的话会很自然就会把 fmap 跟函数合成关联起来（fmap (+3) (*3) 等价于 (+3) . (*3)，也等价于 \x -> ((x*3)+3)），毕竟我们是接受一个函数 (*3) 然后套用 (+3) 转换。最后的结果仍然是一个函数，只是当我们喂给他一个数字的时候，他会先乘上三然后做转换加上三。这基本上就是函数合成在做的事。
Applicative functors
在这个章节中，我们会学到 applicative functors，也就是加强版的 functors，在 Haskell 中是用在 Control.Applicative 中的 Applicative 这个 typeclass 来定义的。
你还记得 Haskell 中函数缺省就是 Curried 的，那代表接受多个参数的函数实际上是接受一个参数然后回传一个接受剩余参数的函数，以此类推。如果一个函数的型别是 a -> b -> c，我们通常会说这个函数接受两个参数并回传 c，但他实际上是接受 a 并回传一个 b -> c 的函数。这也是为什么我们可以用 (f x) y 的方式调用 f x y。这个机制让我们可以 partially apply 一个函数，可以用比较少的参数调用他们。可以做成一个函数再喂给其他函数。
到目前为止，当我们要对 functor map over 一个函数的时候，我们用的函数都是只接受一个参数的。但如果我们要 map 一个接受两个参数的函数呢？我们来看几个具体的例子。如果我们有 Just 3 然后我们做 fmap (*) (Just 3)，那我们会获得什么样的结果？从 Maybe 对 Functor 的 instance 实作来看，我们知道如果他是 Just something，他会对在 Just 中的 something 做映射。因此当 fmap (*) (Just 3) 会得到 Just ((*) 3)，也可以写做 Just (* 3)。我们得到了一个包在 Just 中的函数。
ghci> :t fmap (++) (Just "hey")  
fmap (++) (Just "hey") :: Maybe ([Char] -> [Char])  
ghci> :t fmap compare (Just 'a')  
fmap compare (Just 'a') :: Maybe (Char -> Ordering)  
ghci> :t fmap compare "A LIST OF CHARS"  
fmap compare "A LIST OF CHARS" :: [Char -> Ordering]  
ghci> :t fmap (\x y z -> x + y / z) [3,4,5,6]  
fmap (\x y z -> x + y / z) [3,4,5,6] :: (Fractional a) => [a -> a -> a]
如果我们 map compare 到一个包含许多字符的 list 呢？他的型别是 (Ord a) => a -> a -> Ordering，我们会得到包含许多 Char -> Ordering 型别函数的 list，因为 compare 被 partially apply 到 list 中的字符。他不是包含许多 (Ord a) => a -> Ordering 的函数，因为第一个 a 碰到的型别是 Char，所以第二个 a 也必须是 Char。
我们看到如何用一个多参数的函数来 map functor，我们会得到一个包含了函数的 functor。那现在我们能对这个包含了函数的 functor 做什么呢？我们能用一个吃这些函数的函数来 map over 这个 functor，这些在 functor 中的函数都会被当作参数丢给我们的函数。
ghci> let a = fmap (*) [1,2,3,4]  
ghci> :t a  
a :: [Integer -> Integer]  
ghci> fmap (\f -> f 9) a  
[9,18,27,36]
但如果我们的有一个 functor 里面是 Just (3 *) 还有另一个 functor 里面是 Just 5，但我们想要把第一个 Just (3 *) map over Just 5 呢？如果是普通的 functor，那就没救了。因为他们只允许 map 一个普通的函数。即使我们用 \f -> f 9 来 map 一个装了很多函数的 functor，我们也是使用了普通的函数。我们是无法单纯用 fmap 来把包在一个 functor 的函数 map 另一个包在 functor 中的值。我们能用模式匹配 Just 来把函数从里面抽出来，然后再 map Just 5，但我们是希望有一个一般化的作法，对任何 functor 都有效。
我们来看看 Applicative 这个 typeclass。他位在 Control.Applicative 中，在其中定义了两个函数 pure 跟 <*>。他并没有提供缺省的实作，如果我们想使用他必须要为他们 applicative functor 的实作。typeclass 定义如下：
class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b
这简简单单的三行可以让我们学到不少。首先来看第一行。他开启了 Applicative 的定义，并加上 class contraint。描述了一个型别构造子要是 Applicative，他必须也是 Functor。这就是为什么我们说一个型别构造子属于 Applicative 的话，他也会是 Functor，因此我们能对他使用 fmap。
第一个定义的是 pure。他的型别宣告是 pure :: a -> f a。f 代表 applicative functor 的 instance。由于 Haskell 有一个优秀的型别系统，其中函数又是将一些参数映射成结果，我们可以从型别宣告中读出许多消息。pure 应该要接受一个值，然后回传一个包含那个值的 applicative functor。我们这边是用盒子来作比喻，即使有一些比喻不完全符合现实的情况。尽管这样，a -> f a 仍有许多丰富的信息，他确实告诉我们他会接受一个值并回传一个 applicative functor，里面装有结果。
对于 pure 比较好的说法是把一个普通值放到一个缺省的 context 下，一个最小的 context 但仍然包含这个值。
<*> 也非常有趣。他的型别是 f (a -> b) -> f a -> f b。这有让你联想到什么吗？没错！就是 fmap :: (a -> b) -> f a -> f b。他有点像加强版的 fmap。然而 fmap 接受一个函数跟一个 functor，然后套用 functor 之中的函数。<*> 则是接受一个装有函数的 functor 跟另一个 functor，然后取出第一个 functor 中的函数将他对第二个 functor 中的值做 map。
我们来看看 Maybe 的 Applicative 实作：
instance Applicative Maybe where  
    pure = Just  
    Nothing <*> _ = Nothing  
    (Just f) <*> something = fmap f something
从 class 的定义我们可以看到 f 作为 applicative functor 会接受一个具体型别当作参数，所以我们是写成 instance Applicative Maybe where 而不是写成 instance Applicative (Maybe a) where。
首先看到 pure。他只不过是接受一个东西然后包成 applicative functor。我们写成 pure = Just 是因为 Just 不过就是一个普通函数。我们其实也可以写成 pure x = Just x。
接着我们定义了 <*>。我们无法从 Nothing 中抽出一个函数，因为 Nothing 并不包含一个函数。所以我们说如果我们要尝试从 Nothing 中取出一个函数，结果必定是 Nothing。如果你看看 Applicative 的定义，你会看到他有 Functor 的限制，他代表 <*> 的两个参数都会是 functors。如果第一个参数不是 Nothing，而是一个装了函数的 Just，而且我们希望将这个函数对第二个参数做 map。这个也考虑到第二个参数是 Nothing 的情况，因为 fmap 任何一个函数至 Nothing 会回传 Nothing。
对于 Maybe 而言，如果左边是 Just，那 <*> 会从其中抽出了一个函数来 map 右边的值。如果有任何一个参数是 Nothing。那结果便是 Nothing。
来试试看吧！
ghci> Just (+3) <*> Just 9  
Just 12  
ghci> pure (+3) <*> Just 10  
Just 13  
ghci> pure (+3) <*> Just 9  
Just 12  
ghci> Just (++"hahah") <*> Nothing  
Nothing  
ghci> Nothing <*> Just "woot"  
Nothing
我们看到 pure (+3) 跟 Just (+3) 在这个 case 下是一样的。如果你是在 applicative context 底下跟 Maybe 打交道的话请用 pure，要不然就用 Just。前四个输入展示了函数是如何被取出并做 map 的动作，但在这个 case 底下，他们同样也可以用 unwrap 函数来 map over functors。最后一行比较有趣，因为我们试着从 Nothing 取出函数并将他 map 到某个值。结果当然是 Nothing。
对于普通的 functors，你可以用一个函数 map over 一个 functors，但你可能没办法拿到结果。而 applicative functors 则让你可以用单一一个函数操作好几个 functors。看看下面一段代码：
ghci> pure (+) <*> Just 3 <*> Just 5  
Just 8  
ghci> pure (+) <*> Just 3 <*> Nothing  
Nothing  
ghci> pure (+) <*> Nothing <*> Just 5  
Nothing
究竟我们写了些什么？我们来一步步看一下。<*> 是 left-associative，也就是说 pure (+) <*> Just 3 <*> Just 5 可以写成 (pure (+) <*> Just 3) <*> Just 5。首先 + 是摆在一个 functor 中，在这边刚好他是一个 Maybe。所以首先，我们有 pure (+)，他等价于 Just (+)。接下来由于 partial application 的关系，Just (+) <*> Just 3 等价于 Just (3+)。把一个 3 喂给 + 形成另一个只接受一个参数的函数，他的效果等于加上 3。最后 Just (3+) <*> Just 5 被运算，其结果是 Just 8。
这样很棒吧！用 applicative style 的方式来使用 applicative functors。像是 pure f <*> x <*> y <*> ... 就让我们可以拿一个接受多个参数的函数，而且这些参数不一定是被包在 functor 中。就这样来套用在多个在 functor context 的值。这个函数可以吃任意多的参数，毕竟 <*> 只是做 partial application 而已。
如果我们考虑到 pure f <*> x 等于 fmap f x 的话，这样的用法就更方便了。这是 applicative laws 的其中一条。我们稍后会更仔细地查看这条定律。现在我们先依直觉来使用他。就像我们先前所说的，pure 把一个值放进一个缺省的 context 中。如果我们要把一个函数放在一个缺省的 context，然后把他取出并套用在放在另一个 applicative functor 的值。我们会做的事就是把函数 map over 那个 applicative functor。但我们不会写成 pure f <*> x <*> y <*> ...，而是写成 fmap f x <*> y <*> ...。这也是为什么 Control.Applicative 会 export 一个函数 <$>，他基本上就是中缀版的 fmap。他是这么被定义的：
(<$>) :: (Functor f) => (a -> b) -> f a -> f b  
f <$> x = fmap f x
要记住型别变量跟参数的名字还有值绑定的名称不冲突。``f`` 在函数的型别宣告中是型别变量，说明 ``f`` 应该要满足 ``Functor`` typeclass 的条件。而在函数本体中的 ``f`` 则表示一个函数，我们将他 map over x。我们同样用 ``f`` 来表示他们并代表他们是相同的东西。
<$> 的使用显示了 applicative style 的好处。如果我们想要将 f 套用三个 applicative functor。我们可以写成 f <$> x <*> y <*> z。如果参数不是 applicative functor 而是普通值的话。我们则写成 f x y z。
我们再仔细看看他是如何运作的。我们有一个 Just "johntra" 跟 Just "volta" 这样的值，我们希望将他们结合成一个 String，并且包含在 Maybe 中。我们会这样做：
ghci> (++) <$> Just "johntra" <*> Just "volta"  
Just "johntravolta"
可以将上面的跟下面这行比较一下：
ghci> (++) "johntra" "volta"  
"johntravolta"
可以将一个普通的函数套用在 applicative functor 上真不错。只要稍微写一些 <$> 跟 <*> 就可以把函数变成 applicative style，可以操作 applicatives 并回传 applicatives。
总之当我们在做 (++) <$> Just "johntra" <*> Just "volta" 时，首先我们将 (++) map over 到 Just "johntra"，然后产生 Just ("johntra"++)，其中 (++) 的型别为 (++) :: [a] -> [a] -> [a]，Just ("johntra"++) 的型别为 Maybe ([Char] -> [Char])。注意到 (++) 是如何吃掉第一个参数，以及我们是怎么决定 a 是 Char 的。当我们做 Just ("johntra"++) <*> Just "volta"，他接受一个包在 Just 中的函数，然后 map over Just "volta"，产生了 Just "johntravolta"。如果两个值中有任意一个为 Nothing，那整个结果就会是 Nothing。
到目前为止我们只有用 Maybe 当作我们的案例，你可能也会想说 applicative functor 差不多就等于 Maybe。不过其实有许多其他 Applicative 的 instance。我们来看看有哪些。
List 也是 applicative functor。很惊讶吗？来看看我们是怎么定义 [] 为 Applicative 的 instance 的。
instance Applicative [] where  
    pure x = [x]  
    fs <*> xs = [f x | f <- fs, x <- xs]
早先我们说过 pure 是把一个值放进缺省的 context 中。换种说法就是一个会产生那个值的最小 context。而对 list 而言最小 context 就是 []，但由于空的 list 并不包含一个值，所以我们没办法把他当作 pure。这也是为什么 pure 其实是接受一个值然后回传一个包含单元素的 list。同样的，Maybe 的最小 context 是 Nothing，但他其实表示的是没有值。所以 pure 其实是被实作成 Just 的。
ghci> pure "Hey" :: [String]  
["Hey"]  
ghci> pure "Hey" :: Maybe String  
Just "Hey"
至于 <*> 呢？如果我们假定 <*> 的型别是限制在 list 上的话，我们会得到 (<*>) :: [a -> b] -> [a] -> [b]。他是用 list comprehension 来实作的。<*> 必须要从左边的参数取出函数，将他 map over 右边的参数。但左边的 list 有可能不包含任何函数，也可能包含一个函数，甚至是多个函数。而右边的 list 有可能包含多个值。这也是为什么我们用 list comprehension 的方式来从两个 list 取值。我们要对左右任意的组合都做套用的动作。而得到的结果就会是左右两者任意组合的结果。
ghci> [(*0),(+100),(^2)] <*> [1,2,3]  
[0,0,0,101,102,103,1,4,9]
左边的 list 包含三个函数，而右边的 list 有三个值。所以结果会是有九个元素的 list。在左边 list 中的每一个函数都被套用到右边的值。如果我们今天在 list 中的函数是接收两个参数的，我们也可以套用到两个 list 上。
ghci> [(+),(*)] <*> [1,2] <*> [3,4]  
[4,5,5,6,3,4,6,8]
由于 <*> 是 left-associative，也就是说 [(+),(*)] <*> [1,2] 会先运作，产生 [(1+),(2+),(1*),(2*)]。由于左边的每一个函数都套用至右边的每一个值。也就产生 [(1+),(2+),(1*),(2*)] <*> [3,4]，其便是最终结果。
list 的 applicative style 是相当有趣的：
ghci> (++) <$> ["ha","heh","hmm"] <*> ["?","!","."]  
["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."]
看看我们是如何将一个接受两个字串参数的函数套用到两个 applicative functor 上的，只要用适当的 applicative 运算子就可以达成。
你可以将 list 看作是一个 non-deterministic 的计算。而对于像 100 或是 "what" 这样的值则是 deterministic 的计算，只会有一个结果。而 [1,2,3] 则可以看作是没有确定究竟是哪一种结果。所以他代表的是所有可能的结果。当你在做 (+) <$> [1,2,3] <*> [4,5,6]，你可以想做是把两个 non-deterministic 的计算做 +，只是他会产生另一个 non-deterministic 的计算，而且结果更加不确定。
Applicative style 对于 list 而言是一个取代 list comprehension 的好方式。在第二章中，我们想要看到 [2,5,10] 跟 [8,10,11] 相乘的结果，所以我们这样做：
ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]     
[16,20,22,40,50,55,80,100,110]
我们只是从两个 list 中取出元素，并将一个函数套用在任何元素的组合上。这也可以用 applicative style 的方式来写：
ghci> (*) <$> [2,5,10] <*> [8,10,11]  
[16,20,22,40,50,55,80,100,110]
这写法对我来说比较清楚。可以清楚表达我们是要对两个 non-deterministic 的计算做 *。如果我们想要所有相乘大于 50 可能的计算结果，我们会这样写：
ghci> filter (>50) $ (*) <$> [2,5,10] <*> [8,10,11]  
[55,80,100,110]
很容易看到 pure f <*> xs 等价于 fmap f xs。而 pure f 就是 [f]，而且 [f] <*> xs 可将左边的每个函数套用至右边的每个值。但左边其实只有一个函数，所以他做起来就像是 mapping。
另一个我们已经看过的 Applicative 的 instance 是 IO，来看看他是怎么实作的：
instance Applicative IO where  
    pure = return  
    a <*> b = do  
        f <- a  
        x <- b  
        return (f x)
由于 pure 是把一个值放进最小的 context 中，所以将 return 定义成 pure 是很合理的。因为 return 也是做同样的事情。他做了一个不做任何事情的 I/O action，他可以产生某些值来作为结果，但他实际上并没有做任何 I/O 的动作，例如说印出结果到终端或是文件。
如果 <*> 被限定在 IO 上操作的话，他的型别会是 (<*>) :: IO (a -> b) -> IO a -> IO b。他接受一个产生函数的 I/O action，还有另一个 I/O action，并从以上两者创造一个新的 I/O action，也就是把第二个参数喂给第一个参数。而得到回传的结果，然后放到新的 I/O action 中。我们用 do 的语法来实作他。你还记得的话 do 就是把好几个 I/O action 黏在一起，变成一个大的 I/O action。
而对于 Maybe 跟 [] 而言，我们可以把 <*> 想做是从左边的参数取出一个函数，然后套用到右边的参数上。至于 IO，这种取出的模拟方式仍然适用，但我们必须多加一个 sequencing 的概念，因为我们是从两个 I/O action 中取值，也是在 sequencing，把他们黏成一个。我们从第一个 I/O action 中取值，但要取出 I/O action 的结果，他必须要先被执行过。
考虑下面这个范例：
myAction :: IO String  
myAction = do  
    a <- getLine  
    b <- getLine  
    return $ a ++ b
这是一个提示用户输入两行并产生将两行输入串接在一起结果的一个 I/O action。我们先把两个 getLine 黏在一起，然后用一个 return，这是因为我们想要这个黏成的 I/O action 包含 a ++ b 的结果。我们也可以用 applicative style 的方式来描述：
myAction :: IO String  
myAction = (++) <$> getLine <*> getLine
我们先前的作法是将两个 I/O action 的结果喂给函数。还记得 getLine 的型别是 getLine :: IO String。当我们对 applicative functor 使用 <*> 的时候，结果也会是 applicative functor。
如果我们再使用盒子的模拟，我们可以把 getLine 想做是一个去真实世界中拿取字串的盒子。而 (++) <$> getLine <*> getLine 会创造一个比较大的盒子，这个大盒子会派两个盒子去终端拿取字串，并把结果串接起来放进自己的盒子中。
(++) <$> getLine <*> getLine 的型别是 IO String，他代表这个表达式式一个再普通不过的 I/O action，他里面也装着某种值。这也是为什么我们可以这样写：
main = do  
    a <- (++) <$> getLine <*> getLine  
    putStrLn $ "The two lines concatenated turn out to be: " ++ a
如果你发现你是在做 binding I/O action 的动作，而且在 binding 之后还调用一些函数，最后用 return 来将结果包起来。 那你可以考虑使用 applicative style，这样可以更简洁。
另一个 Applicative 的 instance 是 (->) r。虽然他们通常是用在 code golf 的情况，但他们还是十分有趣的例子。所以我们还是来看一下他们是怎么被实作的。
如果你忘记 ``(->) r`` 的意思，回去翻翻前一章节我们介绍 ``(->) r`` 作为一个 functor 的范例。
instance Applicative ((->) r) where  
    pure x = (\_ -> x)  
    f <*> g = \x -> f x (g x)
当我们用 pure 将一个值包成 applicative functor 的时候，他产生的结果永远都会是那个值。也就是最小的 context。那也是为什么对于 function 的 pure 实作来讲，他就是接受一个值，然后造一个函数永远回传那个值，不管他被喂了什么参数。如果你限定 pure 的型别至 (->) r 上，他就会是 pure :: a -> (r -> a)。
ghci> (pure 3) "blah"  
3
由于 currying 的关系，函数套用是 left-associative，所以我们忽略掉括弧。
ghci> pure 3 "blah"  
3
而 <*> 的实作是比较不容易了解的，我们最好看一下怎么用 applicative style 的方式来使用作为 applicative functor 的 function。
ghci> :t (+) <$> (+3) <*> (*100)  
(+) <$> (+3) <*> (*100) :: (Num a) => a -> a  
ghci> (+) <$> (+3) <*> (*100) $ 5  
508
将两个 applicative functor 喂给 <*> 可以产生一个新的 applicative functor，所以如果我们丢给他两个函数，我们能得到一个新的函数。所以是怎么一回事呢？当我们做 (+) <$> (+3) <*> (*100)，我们是在实作一个函数，他会将 (+3) 跟 (*100) 的结果再套用 +。要看一个实际的范例的话，可以看一下 (+) <$> (+3) <*> (*100) $ 5 首先 5 被丢给 (+3) 跟 (*100)，产生 8 跟 500。然后 + 被套用到 8 跟 500，得到 508。
ghci> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5  
[8.0,10.0,2.5]
这边也一样。我们创建了一个函数，他会调用 \x y z -> [x,y,z]，而丢的参数是 (+3), (*2) 跟 (/2)。5 被丢给以上三个函数，然后他们结果又接到 \x y z -> [x, y, z]。
你可以将函数想做是装着最终结果的盒子，所以 k <$> f <*> g 会制造一个函数，他会将 f 跟 g 的结果丢给 k。当我们做 (+) <$> Just 3 <*> Just 5，我们是用 + 套用在一些可能有或可能没有的值上，所以结果也会是可能有或没有。当我们做 (+) <$> (+10) <*> (+5)，我们是将 + 套用在 (+10) 跟 (+5) 的结果上，而结果也会是一个函数，当被喂给一个参数的时候会产生结果。
我们通常不会将函数当作 applicative 用，不过仍然值得当作练习。对于 (->) r 怎么定义成 Applicative 的并不是真的那么重要，所以如果你不是很懂的话也没关系。这只是让你获得一些操作上的直觉罢了。
一个我们之前还没碰过的 Applicative 的 instance 是 ZipList，他是包含在 Control.Applicative 中。
对于 list 要作为一个 applicative functor 可以有多种方式。我们已经介绍过其中一种。如果套用 <*>，左边是许多函数，而右边是许多值，那结果会是函数套用到值的所有组合。如果我们做 [(+3),(*2)] <*> [1,2]。那 (+3) 会先套用至 1 跟 2。接着 (*2) 套用至 1 跟 2。而得到 [4,5,2,4]。
然而 [(+3),(*2)] <*> [1,2] 也可以这样运作:把左边第一个函数套用至右边第一个值，接着左边第二个函数套用右边第二个值，以此类推。这样得到的会是 [4,4]。或是 [1 + 3, 2 * 2]。
由于一个型别不能对同一个 typeclass 定义两个 instance，所以才会定义了 ZipList a，他只有一个构造子 ZipList，他只包含一个字段，他的型别是 list。
instance Applicative ZipList where  
        pure x = ZipList (repeat x)  
        ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)
<*> 做的就是我们之前说的。他将第一个函数套用至第一个值，第二个函数套用第二个值。这也是 zipWith (\f x -> f x) fs xs 做的事。由于 zipWith 的特性，所以结果会跟 list 中比较短的那个一样长。
pure 也值得我们讨论一下。他接受一个值，把他重复地放进一个 list 中。pure "haha" 就会是 ZipList (["haha","haha","haha"...。这可能会造成些混淆，毕竟我们说过 pure 是把一个值放进一个最小的 context 中。而你会想说无限长的 list 不可能会是一个最小的 context。但对于 zip list 来说这是很合理的，因为他必须在 list 的每个位置都有值。这也遵守了 pure f <*> xs 必须要等价于 fmap f xs 的特性。如果 pure 3 只是回传 ZipList [3]，那 pure (*2) <*> ZipList [1,5,10] 就只会算出 ZipList [2]，因为两个 zip list 算出结果的长度会是比较短的那个的长度。如果我们 zip 一个有限长的 list 以及一个无限长的 list，那结果的长会是有限长的 list 的长度。
那 zip list 是怎么用 applicative style 操作的呢？我们来看看，ZipList a 型别并没有定义成 Show 的 instance，所以我们必须用 getZipList 函数来从 zip list 取出一个普通的 list。
ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100,100]  
[101,102,103]  
ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100..]  
[101,102,103]  
ghci> getZipList $ max <$> ZipList [1,2,3,4,5,3] <*> ZipList [5,3,1,2]  
[5,3,3,4]  
ghci> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "cat" <*> ZipList "rat"  
[('d','c','r'),('o','a','a'),('g','t','t')]
``(,,)`` 函数跟 ``\x y z -> (x,y,z)`` 是等价的，而 ``(,)`` 跟 ``\x y -> (x,y)`` 是等价的。
除了 zipWith，标准函式库中也有 zipWith3, zipWith4 之类的函数，最多支持到 7。zipWith 接受一个接受两个参数的函数，并把两个 list zip 起来。zipWith3 则接受一个接受三个参数的函数，然后把三个 list zip 起来。以此类推。用 applicative style 的方式来操作 zip list 的话，我们就不需要对每个数量的 list 都定义一个独立的 zip 函数来 zip 他们。我们只需要用 applicative style 的方式来把任意数量的 list zip 起来就可以了。
Control.Applicative 定义了一个函数叫做 liftA2，他的型别是 liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c。他定义如下：
liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c  
liftA2 f a b = f <$> a <*> b
并没有太难理解的东西，他不过就是对两个 applicatives 套用函数而已，而不用我们刚刚熟悉的 applicative style。我们提及他的理由只是要展示为什么 applicative functors 比起一般的普通 functor 要强。如果只是普通的 functor 的话，我们只能将一个函数 map over 这个 functor。但有了 applicative functor，我们可以对好多个 functor 套用一个函数。看看这个函数的型别，他会是 (a -> b -> c) -> (f a -> f b -> f c)。当我们从这样的角度来看他的话，我们可以说 liftA2 接受一个普通的二元函数，并将他升级成一个函数可以运作在两个 functor 之上。
另外一个有趣的概念是，我们可以接受两个 applicative functor 并把他们结合成一个 applicative functor，这个新的将这两个 applicative functor 装在 list 中。举例来说，我们现在有 Just 3 跟 Just 4。我们假设后者是一个只包含单元素的 list。
ghci> fmap (\x -> [x]) (Just 4)  
Just [4]
所以假设我们有 Just 3 跟 Just [4]。我们有怎么得到 Just [3,4] 呢？很简单。
ghci> liftA2 (:) (Just 3) (Just [4])  
Just [3,4]  
ghci> (:) <$> Just 3 <*> Just [4]  
Just [3,4]
还记得 : 是一个函数，他接受一个元素跟一个 list，并回传一个新的 list，其中那个元素已经接在前面。现在我们有了 Just [3,4]，我们能够将他跟 Just 2 绑在一起变成 Just [2,3,4] 吗？当然可以。我们可以将任意数量的 applicative 绑在一起变成一个 applicative，里面包含一个装有结果的 list。我们试着实作一个函数，他接受一串装有 applicative 的 list，然后回传一个 applicative 里面有一个装有结果的 list。我们称呼他为 sequenceA。
sequenceA :: (Applicative f) => [f a] -> f [a]  
sequenceA [] = pure []  
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs
居然用到了递归！首先我们来看一下他的型别。他将一串 applicative 的 list 转换成一个 applicative 装有一个 list。从这个信息我们可以推测出边界条件。如果我们要将一个空的 list 变成一个装有 list 的 applicative。我们只要把这个空的 list 放进一个缺省的 context。现在来看一下我们怎么用递归的。如果们有一个可以分成头跟尾的 list（x 是一个 applicative 而 xs 是一串 applicatve），我们可以对尾巴调用 sequenceA，便会得到一个装有 list 的 applicative。然后我们只要将在 x 中的值把他接到装有 list 的 applicative 前面就可以了。
所以如果我们做 sequenceA [Just 1, Just 2]，也就是 (:) <$> Just 1 <*> sequenceA [Just 2]。那会等价于 (:) <$> Just 1 <*> ((:) <$> Just 2 <*> sequenceA [])。我们知道 sequenceA [] 算出来会是 Just []，所以运算式就变成 (:) <$> Just 1 <*> ((:) <$> Just 2 <*> Just [])，也就是 (:) <$> Just 1 <*> Just [2]，算出来就是 Just [1,2]。
另一种实作 sequenceA 的方式是用 fold。要记得几乎任何需要走遍整个 list 并 accumulate 成一个结果的都可以用 fold 来实作。
sequenceA :: (Applicative f) => [f a] -> f [a]  
sequenceA = foldr (liftA2 (:)) (pure [])
我们从右往左走，并且起始的 accumulator 是用 pure []。我们是用 liftA2 (:) 来结合 accumulator 跟 list 中最后的元素，而得到一个 applicative，里面装有一个单一元素的一个 list。然后我们再用 liftA2 (:) 来结合 accumulator 跟最后一个元素，直到我们只剩下 accumulator 为止，而得到一个 applicative，里面装有所有结果。
我们来试试看套用在不同 applicative 上。
ghci> sequenceA [Just 3, Just 2, Just 1]  
Just [3,2,1]  