Haskell/Applicative 函子

Applicative 函子 (解决方案)

高级 Haskell

Monoids
Applicative 函子
 可折叠
 可遍历
 箭头教程
 理解箭头
延续传递风格
 拉链
透镜
 共函子
值递归 (MonadFix)
有副作用的流
 可变对象
并发
模板 Haskell
类型族

在介绍重要的 Functor 和 Monad 类型类时，我们忽略了第三个类型类：Applicative，这是应用函子的类。与单子一样，应用函子是具有额外定律和操作的函子；实际上，Applicative 是介于 Functor 和 Monad 之间的中间类。Applicative 是一个广泛使用的类，拥有丰富的应用。它实现了同名的应用风格，这是一种构建函子计算的便捷方式，还提供了表达许多重要模式的方法。

`Functor` 回顾

我们将从快速回顾 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 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` 的结果，所得结果相同。^[1]

还有一个关于 `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` 和 `(<*>)` ^[2]。

pure = return
(<*>) = ap

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

许多其他单子函数拥有更通用的应用函数版本。以下列出了一些例子。

单子	应用函数	模块 (在哪里可以找到应用函数版本)
`(>>)`	`(*>)`	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`

列表也是应用函子。专门针对列表而言，`(<*>)` 的类型变为…

[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-list 中工作；只需要添加 `newtype` 包装器即可

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

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

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-list 中的所有元素。确保 `zipWith ($) fs` 从不删除元素的唯一方法是使 `fs` 为无限。正确的 `pure` 遵循这一点

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

`ZipList` 应用实例提供了一种替代方法，可以代替 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` 中值的存在）。`[]` 作为非交换应用函子，其 `(<*>)` 的两种合法实现仅在效果的排序方面有所不同。相比之下，交换应用函子在这方面没有歧义。更正式地说，交换应用函子是指满足以下条件的函子

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` 的情况，它具有交换性

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 中的约定是始终使用从左到右的排序来实现 `(<*>)` 和其他应用运算符。虽然这种约定有助于减少混淆，但它也意味着外观有时会具有误导性。例如，`(<*)` 函数不是 `flip (*>)`，因为它与 `(*>)` 一样，从左到右排序效果

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

出于同样的原因，来自 `Control.Applicative` 的 `(<**>) :: Applicative f => f a -> f (a -> b) -> f b` 不是 `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`。
以下应用函子是否具有交换性？
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` 上^[3]。它们之间的区别在于每个情况下被映射的内容

`fmap` 将任意函数映射到函子上。
`(<*>)` 将 `t (a -> b)` 态射映射到（应用）函子上。
`(=<<)` 将 `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 将 t 的一个分支替换为带有默认值 z 的叶节点，只要它上面直接的任何叶节点满足测试 p。
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)

名称“单子”背后有深刻的理论原因 ^[4]。无论如何，我们可以非正式地说，它看起来非常像一个幺半群：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)`