Haskell/Applicative 函子

在介绍重要的 Functor 和 Monad 类型类时，我们忽略了第三个类型类：Applicative，即 *应用函子* 的类。与单子一样，应用函子是具有额外定律和操作的函子；事实上，Applicative 是 Functor 和 Monad 之间的中间类。Applicative 是一个广泛使用的类，有着丰富的应用。它支持同名的 *应用风格*，这是一种方便的函子计算结构方式，也提供了表达一些重要模式的方法。

Functor 回顾

我们将从快速回顾 函子类章节 开始。Functor 的特征是 fmap 函数

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

如果一个类型是 Functor 的实例，你可以使用 fmap 将函数应用于其中的值。另一种描述 fmap 的方法是说它将函数提升以作用于函子值。为了确保 fmap 正常工作，Functor 的任何实例都必须遵守以下两条定律

fmap id = id                   -- 1st functor law
fmap (g . f) = fmap g . fmap f -- 2nd functor law

例如，Maybe 有一个 Functor 实例，因此我们可以轻松地修改它内部的值...

Prelude> fmap negate (Just 2)
Just (-2)

...当然，只要它存在。

Prelude> fmap negate Nothing
Nothing

fmap 有一个中缀同义词 (<$>)。它通常有助于提高可读性，也表明了 fmap 如何被看作是不同类型的函数应用。

Prelude> negate <$> Just 2
Just (-2)

练习
为以下类型定义 Functor 的实例 一棵玫瑰树，定义为：data Tree a = Node a [Tree a] 对于固定 e 的 Either e。 函数类型 ((->) r)。在这种情况下，f a 将是 (r -> a)

函子中的应用

fmap 虽然有用，但如果我们想将一个有两个参数的函数应用于函子值，它就无能为力了。例如，我们如何将 Just 2 和 Just 3 相加？暴力方法是将值从 Maybe 包装器中提取出来。但是，这意味着必须对 Nothing 进行繁琐的检查。更糟糕的是：在不同的 Functor 中，提取值可能甚至不是一种选择（想想 IO）。

我们可以使用 fmap 将 (+) 部分应用于第一个参数

Prelude> :t (+) <$> Just 2
(+) <$> Just 2 :: Num a => Maybe (a -> a)

但现在我们被卡住了：我们有一个函数和一个值，两者都被包装在 Maybe 中，而且没有办法将一个应用于另一个。我们能得到的最接近于期望的 Just 5 的方法可能是这样

Prelude> (<$> Just 3) <$> ((+) <$> Just 2)
Just (Just 5)

(注意 (+) <$> Just 2 是 Just (2+))。

我们希望有一个运算符，它的类型类似于 f (a -> b) -> f a -> f b，以便在函子的上下文中应用函数。如果该运算符被称为 (<*>)，我们就可以写成

(+) <$> Just 2 <*> Just 3

瞧，它起作用了！

Prelude> (+) <$> Just 2 <*> Just 3
Just 5

(<*>) 的类型是

Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

(<*>) 是 Applicative 的方法之一，Applicative 是 *应用函子* 的类型类——支持在其上下文中进行函数应用的函子。像 (+) <$> Just 2 <*> Just 3 这样的表达式被称为用 *应用风格* 编写，这与我们在使用函子时进行常规函数应用的距离最近。如果你暂时假装 (<$>)、(<*>) 和 Just 不存在，我们的示例看起来就像 (+) 2 3。

Applicative 类

Applicative 的定义是

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

除了 (<*>) 之外，该类还有一个第二种方法 pure，它将任意值引入函子。举个例子，让我们看看 Maybe 实例

instance Applicative Maybe where
    pure                  = Just
    (Just f) <*> (Just x) = Just (f x)
    _        <*> _        = Nothing

它没有做任何令人惊讶的事情：pure 用 Just 包装值；(<*>) 将函数应用于值（如果两者都存在），否则会产生 Nothing。

Applicative 函子定律

注意

由于缺乏更好的简写，在接下来的内容中，我们将使用术语 *态射* 来指代 (<*>) 左侧的值，它们符合 Applicative f => f (a -> b) 类型；也就是说，插入应用函子的函数式事物。“态射” 是一个来自范畴论的术语，它有更广泛的含义，但现在我们不必担心它。

就像 Functor 一样，Applicative 有一套合理的实例应该遵循的定律。它们是

pure id <*> v = v                            -- Identity
pure f <*> pure x = pure (f x)               -- Homomorphism
u <*> pure y = pure ($ y) <*> u              -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition

这些定律有点拗口。如果你将 pure 视为将值以默认的、无特征的方式注入函子的方法，这样一来结果就会尽可能接近于普通值，那么它们就更容易理解了。因此

• 恒等律表明，应用 pure id 态射不会有任何作用，这与使用普通 id 函数完全一样。
• 同态律表明，将一个“纯”函数应用于一个“纯”值，与以普通方式将函数应用于该值，然后对结果使用 pure 相同。从某种意义上说，这意味着 pure 保留了函数应用。
• 交换律表明，将一个态射应用于一个“纯”值 pure y，与将 pure ($ y) 应用于该态射相同。这并不奇怪——正如我们在 高阶函数章节 中所看到的，($ y) 是将 y 作为参数提供给另一个函数的函数。
• 组合律表明，pure (.) 以类似于 (.) 组合函数的方式组合态射：将组合态射 pure (.) <*> u <*> v 应用于 w，与将 u 应用于将 v 应用于 w 的结果相同。

还有一个关于 fmap 和 (<*>) 之间关系的额外定律

fmap f x = pure f <*> x                      -- fmap

使用 (<*>) 应用一个“纯”函数，等同于使用 fmap。这条定律是其他定律的结果，因此你在编写 Applicative 的实例时不必费心去证明它。

练习
检查该实例中Maybe是否满足 Applicative 定律 为以下类型编写 Applicative 实例： a. Either e，其中 e 为固定值 b. ((->) r)，其中 r 为固定值

似曾相识

pure 是否让你想起什么？

pure :: Applicative f => a -> f a

它与... 的唯一区别是...

return :: Monad m => a -> m a

... 类约束。pure 和 return 的作用相同，即把值带入函子中。这种奇妙的相似性并没有就此结束。在 关于 State 的章节 中，我们提到了一个名为 ap 的函数...

ap :: (Monad m) => m (a -> b) -> m a -> m b

... 它可以用来使在单子代码中处理具有多个参数的函数更加容易

allTypes :: GeneratorState (Int, Float, Char, Integer, Double, Bool, Int)
allTypes = liftM (,,,,,,) getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom
                     `ap` getRandom

ap 看起来非常像 (<*>)。

当然，这并非巧合。Monad 继承自 Applicative...

Prelude> :info Monad
class Applicative m => Monad (m :: * -> *) where
--etc.

... 因为 return 和 (>>=) 足以实现 pure 和 (<*>) 。

pure = return
(<*>) = ap

ap u v = do
    f <- u
    x <- v
    return (f x)

其他几个单子函数也具有更通用的 Applicative 版本。以下是一些示例：

单子	Applicative	模块 (在哪里可以找到 Applicative 版本)
(>>)	(*>)	Prelude (GHC 7.10+)；Control.Applicative
liftM2	liftA2	Control.Applicative
mapM	traverse	Prelude (GHC 7.10+)；Data.Traversable
sequence	sequenceA	Data.Traversable
forM_	for_	Data.Foldable

练习
使用 (>>=) 和 fmap 编写 (<*>) 的定义。不要使用 do 语法。 实现 liftA5 :: Applicative f => (a -> b -> c -> d -> e -> k) -> f a -> f b -> f c -> f d -> f e -> f k

ZipList

列表也是 Applicative 函子。当专门用于列表时，(<*>) 的类型变为...

[a -> b] -> [a] -> [b]

... 因此，(<*>) 将一个函数列表应用于另一个列表。但具体是如何实现的呢？

列表的标准 Applicative 实例（源于 Monad 实例）将每个函数应用于每个元素，就像 map 的爆炸版本一样。

Prelude> [(2*),(5*),(9*)] <*> [1,4,7]
[2,8,14,5,20,35,9,36,63]

有趣的是，还有另一种将函数列表应用于另一个列表的合理方式。我们可以匹配每个函数与另一个列表中对应位置的值，而不是使用函数和值的每种组合。Prelude 中可以用于此目的的函数是 zipWith

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> zipWith ($) [(2*),(5*),(9*)] [1,4,7]
[2,20,63]

当一个类型存在两种有用的可能实例时，可以通过创建一个实现其中一种实例的 newtype 来解决这个问题。在本例中，我们有 ZipList，它位于 Control.Applicative 中

newtype ZipList a = ZipList { getZipList :: [a] }

我们已经了解了 <*> 应该如何用于 zip 列表；只需要添加 newtype 包装器即可

instance Applicative ZipList where
    (ZipList fs) <*> (ZipList xs) = ZipList (zipWith ($) fs xs)
    pure x                        = undefined -- TODO

至于 pure，我们很想使用 pure x = ZipList [x]，它遵循标准列表实例。然而，我们不能这样做，因为它违反了 Applicative 定律。根据恒等定律

pure id <*> v = v

将 (<*>) 和建议的 pure 代入，我们得到

ZipList [id] <*> ZipList xs = ZipList xs
ZipList (zipWith ($) [id] xs) = ZipList xs

现在，假设 xs 是无限列表 [1..]

ZipList (zipWith ($) [id] [1..]) = ZipList [1..]
ZipList [1] = ZipList [1..]
[1] = [1..] -- Obviously false!

问题在于，zipWith 生成的列表长度与作为参数传递的列表中最短列表的长度相同，因此 (ZipList [id] <*>) 将在第一个元素之后截断另一个 zip 列表的所有元素。确保 zipWith ($) fs 从不移除元素的唯一方法是使 fs 成为无限列表。正确的 pure 应由此得出

instance Applicative ZipList where
    (ZipList fs) <*> (ZipList xs) = ZipList (zipWith ($) fs xs)
    pure x                        = ZipList (repeat x)

ZipList Applicative 实例为 Data.List 中的所有 zipN 和 zipWithN 函数提供了一种替代方案，这些函数可以扩展到任意数量的参数

>>> import Control.Applicative
>>> ZipList [(2*),(5*),(9*)] <*> ZipList [1,4,7]
ZipList {getZipList = [2,20,63]}
>>> (,,) <$> ZipList [1,4,9] <*> ZipList [2,8,1] <*> ZipList [0,0,9]
ZipList {getZipList = [(1,2,0),(4,8,0),(9,1,9)]}
>>> liftA3 (,,) (ZipList [1,4,9]) (ZipList [2,8,1]) (ZipList [0,0,9])
ZipList {getZipList = [(1,2,0),(4,8,0),(9,1,9)]}

效果的排序

正如我们已经看到的那样，列表的标准 Applicative 实例将一个列表中的每个函数应用于另一个列表中的每个元素。然而，这并没有明确地指定 (<*>)。为了说明这一点，请尝试在不查看上面的示例或下面的答案的情况下猜测 [(2*),(3*)]<*>[4,5] 的结果。

Prelude> [(2*),(3*)] <*> [4,5]


--- ...


[8,10,12,15]

除非你非常认真地关注过或已经分析了 (<*>) 的实现，否则猜对的可能性约为一半。另一种可能是 [8,12,10,15]。区别在于，对于第一个（也是正确的）答案，结果是通过获取第一个列表的骨架并将每个元素替换为与第二个列表中的元素的所有可能组合来获得的，而对于另一个可能性，起点是第二个列表。

更一般地说，两者之间的区别在于效果的排序。这里，效果指的是函子上下文，而不是函子内的值（一些示例：列表的骨架，IO 中在现实世界中执行的操作，Maybe 中值的存在）。对于列表存在两种合法的 (<*>) 实现，它们只在效果的排序方面有所不同，这表明 [] 是一个非交换 Applicative 函子。相反，交换 Applicative 函子在这方面不会留下任何模糊的空间。更正式地说，交换 Applicative 函子满足以下条件：

liftA2 f u v = liftA2 (flip f) v u -- Commutativity

或者，等效地：

f <$> u <*> v = flip f <$> v <*> u

顺便说一句，如果你在 Haskell 中听到交换单子，则涉及的概念是相同的，只是专门用于 Monad。

交换性（或非交换性）也会影响从 (<*>) 派生的其他函数。(*>) 就是一个明显的例子

(*>) :: Applicative f => f a -> f b -> f b

(*>) 组合效果，同时只保留其第二个参数的值。对于单子，它等效于 (>>)。以下使用 Maybe 演示了这一点，Maybe 是交换的

Prelude> Just 2 *> Just 3
Just 3
Prelude> Just 3 *> Just 2
Just 2
Prelude> Just 2 *> Nothing
Nothing
Prelude> Nothing *> Just 2
Nothing

交换参数不会影响效果（即，包装值的存与不存在）。但是，对于 IO，交换参数确实会重新排序效果

Prelude> (print "foo" *> pure 2) *> (print "bar" *> pure 3)
"foo"
"bar"
3
Prelude> (print "bar" *> pure 3) *> (print "foo" *> pure 2)
"bar"
"foo"
2

Haskell 中的约定是始终使用从左到右的排序来实现 (<*>) 和其他 Applicative 运算符。尽管此约定有助于减少混淆，但它也意味着外观有时具有误导性。例如，(<*) 函数不是 flip (*>)，因为它像 (*>) 一样从左到右排序效果

Prelude> (print "foo" *> pure 2) <* (print "bar" *> pure 3)
"foo"
"bar"
2

出于同样的原因，(<**>) :: Applicative f => f a -> f (a -> b) -> f b 来自 Control.Applicative，它不是 flip (<*>)。这意味着它提供了一种反转排序的方法

>>> [(2*),(3*)] <*> [4,5]
[8,10,12,15]
>>> [4,5] <**> [(2*),(3*)]
[8,12,10,15]

另一种选择是来自 transformers 的 Control.Applicative.Backwards 模块，它提供了一个用于反转效果顺序的 newtype

newtype Backwards f a = Backwards { forwards :: f a }

>>> Backwards [(2*),(3*)] <*> Backwards [4,5]
Backwards [8,12,10,15]

练习

对于列表函子，从头开始实现（即，不直接使用 Applicative 或 Monad 中的任何内容）(<*>) 及其具有“错误”效果排序的版本， (<|*|>) :: Applicative f => f (a -> b) -> f a -> f b 使用 do 语法改写 Monad 交换性的定义，而不是 ap 或 liftM2。 以下 Applicative 函子是否交换？ a. ZipList b. ((->) r) c. State s（使用 State 章节 中的 newtype 定义。提示：你可能会发现此模块练习 2 的答案很有用。） [2,7,8] *> [3,9] 的结果是什么？（尝试在不写代码的情况下猜测。） 用其他 Applicative 函数实现 (<**>)。 正如我们已经看到的那样，一些函子允许两种合法的 (<*>) 实现，它们只在效果的排序方面有所不同。为什么不存在类似的涉及 (>>=) 的问题？

力量的滑动尺度

Functor、Applicative、Monad。三个紧密相关的函子类型类；三个 Haskell 中最重要的类。尽管我们已经看到了许多 Functor 和 Monad 的使用示例，以及一些 Applicative 的示例，但我们尚未对它们进行并排比较。如果我们暂时忽略 pure/return，那么这三个类的特征方法分别是

fmap :: Functor f => (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(>>=) :: Monad m => m a -> (a -> m b) -> m b

虽然这些类型看起来大相径庭，但我们可以通过一些简单的调整来改变这种局面。我们将 fmap 替换为它的中缀同义词 (<$>)；将 (>>=) 替换为它的反转版本 (=<<)；并稍微整理一下签名

(<$>) :: Functor t     =>   (a ->   b) -> (t a -> t b)
(<*>) :: Applicative t => t (a ->   b) -> (t a -> t b)
(=<<) :: Monad t       =>   (a -> t b) -> (t a -> t b)

突然之间，相似之处显而易见。fmap、(<*>) 和 (=<<) 都是将函数映射到 Functor 上 。它们之间的区别在于每个情况下映射的对象

• fmap 将任意函数映射到函子上。
• (<*>) 将 t (a -> b) 态射 映射到（Applicative）函子上。
• (=<<) 将 a -> t b 函数映射到（单子）函子上。

Functor、Applicative 和 Monad 在日常使用中的区别在于这三个映射函数的类型允许你做什么。从 fmap 到 (<*>) 再到 (>>=)，你的能力、多功能性和控制能力都在增强，但同时也付出了对结果的保证的代价。我们现在将沿着这个尺度进行滑动。在滑动过程中，我们将使用对比术语 _值_ 和 _上下文_ 来分别指代 Functor 中的普通值和围绕它们的任何内容。

fmap 的类型和两个相关的定律确保无论给它什么函数，都不可能使用它来改变上下文。在 (a -> b) -> t a -> t b 中，(a -> b) 函数与 t a 函子值的 t 上下文无关，因此应用它不会影响上下文。因此，如果你对某个列表 xs 执行 fmap f xs，列表的元素数量将永远不会改变。

Prelude> fmap (2*) [2,5,6]
[4,10,12]

这可以被视为安全保证，也可以被视为不幸的限制，这取决于你的意图。无论如何，(<*>) 明显能够改变上下文。

Prelude> [(2*),(3*)] <*> [2,5,6]
[4,10,12,6,15,18]

t (a -> b) 态射自身也带有一个上下文，它与 t a 函子值的上下文相结合。然而，(<*>) 受到更微妙的限制。虽然 t (a -> b) 态射带有上下文，但在它们内部有普通 (a -> b)，它们仍然无法修改上下文。这意味着 (<*>) 对上下文的改变完全由其参数的上下文决定，而值对最终的上下文没有影响。

Prelude> (print "foo" *> pure (2*)) <*> (print "bar" *> pure 3)
"foo"
"bar"
6
Prelude> (print "foo" *> pure 2) *> (print "bar" *> pure 3)
"foo"
"bar"
3
Prelude> (print "foo" *> pure undefined) *> (print "bar" *> pure 3)
"foo"
"bar"
3

因此，对于列表 (<*>)，你知道结果列表的长度将是原始列表长度的乘积；对于 IO (<*>)，你知道只要评估终止，所有现实世界的影响都会发生，等等。

然而，使用 Monad 我们就处于一个完全不同的游戏之中。(>>=) 接受一个 a -> t b 函数，因此它能够从值中创建上下文。这意味着很大的灵活性。

Prelude> [1,2,5] >>= \x -> replicate x x
[1,2,2,5,5,5,5,5]
Prelude> [0,0,0] >>= \x -> replicate x x
[]
Prelude> return 3 >>= \x -> print $ if x < 10 then "Too small" else "OK"
"Too small"
Prelude> return 42 >>= \x -> print $ if x < 10 then "Too small" else "OK"
"OK"

然而，利用额外的灵活性可能意味着对某些内容的保证更少，例如你的函数是否能够意外地擦除数据结构的某些部分，或者你的应用程序中的控制流是否仍然清晰易懂。在某些情况下，也可能存在性能影响，因为单子代码所产生的复杂数据依赖性可能会阻止有用的重构和优化。总而言之，只使用完成手头任务所需的权力是一个好主意。如果你确实需要 Monad 的额外功能，请继续使用；然而，通常值得检查 Applicative 或 Functor 是否足够。

练习

接下来的几个练习涉及以下树形数据结构。 data AT a = L a | B (AT a) (AT a) 为 AT 编写 Functor、Applicative 和 Monad 实例。不要使用诸如 pure = return 之类的快捷方式。Applicative 和 Monad 实例应该匹配；特别是，(<*>) 应该等效于 ap，这从 Monad 实例得出。 实现以下函数，使用 Applicative 实例、Monad 实例或两者都不使用，如果两者都不足以提供解决方案。在 Applicative 和 Monad 之间，选择最不强大的一个，但仍然足够完成任务。在每个案例中用几句话说明你的选择理由。 a. fructify :: AT a -> AT a，它通过将每个叶子 L 替换为包含两个叶子副本的分支 B 来扩展树。 b. prune :: a -> (a -> Bool) -> AT a -> AT a，其中 prune z p t 在任何直接位于其上的叶子满足测试 p 时，用带有默认值 z 的叶子替换 t 的分支。 c. reproduce :: (a -> b) -> (a -> b) -> AT a -> AT b，其中 reproduce f g t 产生一个新的树，其根分支上有两个修改后的 t 副本。左边的副本通过将 f 应用于 t 中的值获得，g 和右边的副本也是如此。 AT 还有另一个合法的 Applicative 实例（原始实例的反向排序版本不算）。写出来。提示：这个其他实例可以用来实现 sagittalMap :: (a -> b) -> (a -> b) -> AT a -> AT b 它在给定一个分支时，将一个函数映射到左子树，另一个函数映射到右子树。 (如果你想知道，"AT" 代表 "苹果树"。植物学家读者，请原谅这些薄弱的比喻。)

单子表示

在 理解单子 中，我们看到了如何使用 (>=>) 或 join 而不是 (>>=) 来指定 Monad 类。类似地，Applicative 也具有另一种表示形式，可以通过以下类型类实现。

class Functor f => Monoidal f where
    unit  :: f ()
    (*&*) :: f a -> f b -> f (a,b)

名称 "单子" 的背后有深刻的理论原因 。无论如何，我们可以非正式地说它看起来非常像一个单子：unit 提供一个默认的函子值，其上下文不包含任何有趣的内容，(*&*) 通过配对值和组合效果来组合函子值。Monoidal 公式更清楚地展示了 Applicative 如何操作函子上下文。当然，unit 和 (*&*) 可以用来定义 pure 和 (<*>)，反之亦然。

Applicative 定律等效于以下定律集，它们是根据 Monoidal 表述的。

fmap snd $ unit *&* v = v                    -- Left identity
fmap fst $ u *&* unit = u                    -- Right identity
fmap asl $ u *&* (v *&* w) = (u *&* v) *&* w -- Associativity
-- asl (x, (y, z)) = ((x, y), z)

($) 左边的函数只是将等效类型（如 b 和 ((), b)）相互转换的样板代码。如果你忽略它们，这些定律比通常的 Applicative 公式不那么不透明。顺便说一下，就像 Applicative 一样，还有一个额外的定律，它保证在 Haskell 中成立。

fmap (g *** h) (u *&* v) = fmap g u *&* fmap h v -- Naturality
-- g *** h = \(x, y) -> (g x, h y)

练习
根据 pure 和 (<*>) 编写 unit 和 (*&*) 的实现，反之亦然。 根据 Monoidal 方法来表述可交换应用函子定律（参见 效果排序 部分）。 从头开始为以下内容编写 Monoidal 实例。 a. ZipList b. ((->) r)