Haskell/Applicative类型类

Applicative类型类 (解答)

高级Haskell

Monoid类型类
 Applicative类型类
 箭头
 理解箭头
 Foldable类型类
 Traversable类型类
 延续过渡风格（CPS）
可变对象
 拉链
 适用函子
 独异点
 Lens 和引用
 并行

此处只翻译了一些其它教程 (主要指《Haskell 趣学指南》) 中没有提及的延伸内容, 关于 Applicative 的基础用法, 请见Haskell 趣学指南.

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

当一个类型有着多种 instance 实现的可能性时, 我们使用 newtype 来避免冲突. 本例中, 我们有 Control.Applicative 包提供的 ZipList:

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

我们已经知道 <*> 应该在 ZipList 上发挥什么作用了; 现在我们只需把它用 newtype 包裹写成代码:

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

至于 pure, 或许我们会想到用 pure x = ZipList [x], 就如同列表的 instance 一样. 然而我们并不能这样做, 因为其会违反 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..] -- 显然不等!

问题在于, zipWith 产生的列表和两个参数中最短的那个长度相同, 因此 (ZipList [id] <*>) 将会舍弃另一个列表中除了第一个外的所有元素. 为了保证 zipWith ($) fs 不舍弃元素, fs 必须是无限的. 因此, 正确的 pure 实现:

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

因为其提供了将任意数量的列表应用在一起的能力, ZipList 的 Applicative instance 能够替代 Data.List 中的 zip* 和 zip*With 函数:

>>> 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 instance 将一个列表中的每一个函数应用到另一个列表中的每一个值上. 但是, (<*>) 仍然并不明了. 比如说, [(2*),(3*)]<*>[4,5] 的结果会是什么呢?

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


--- ...


[8,10,12,15]

除非我们非常留意且仔细分析过 (<*>), 我们大概只有一半的几率答对. 另一种可能性是 [8,12,10,15]. 它们的区别在于, 第一个 (也是正确的那一个) 答案是由使用第一个列表的结构, 将结构中的每一个值和第二个列表中的所有可能的值组合而成的. 而第二种答案则反之.

更概括地说, 其间的区别在于副作用的序列化方式. 这里, "副作用"指的是 Functor 携带的额外信息, 而不是 Functor 中的值 (一些例子是: 列表的结果, 在非纯函数式环境中被执行的 IO, Maybe 中值的存在性). 这两种列表 (<*>) 的可能实现的区别仅在于副作用序列化的方式, 意味着 [] 是一个不满足交换律的 Applicative. 相比之下, 一个满足交换律的 Applicative, 在此方面上不可能存疑. 正式的, 一个满足交换律的 Applicative 满足以下等式:

liftA2 f u v = liftA2 (flip f) v u -- 可交换性

或者等价的,

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

顺便一提, 如果你听说过 Haskell 中满足交换律的 monad, 它们的概念实际上差不多是一致的, 只是这里的对象是 Monad 罢了.

可交换下 (或者不可交换性) 同样影响其它一些由 (<*>) 衍生的函数. 举个例子, (*>):

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

(*>) 在将副作用合并的同时只保留右边参数的值. 它和 monad 的 (>>) 等价. 这是它的一个 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

基于同样的理由, 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]

练习

为列表 functor 实现 (<*>) 和它的"副作用倒置版本"
(<|*|>) :: Applicative f => f (a -> b) -> f a -> f b, 且不使用任何来自 Applicative 或者 Monad 的函数.
使用 do 代码块重写 Monad 的交换律, 不使用 ap 或 liftM2.
以下的 Applicative 满足交换律吗?
a. ZipList
b. ((->) r)
c. State s (使用这个定义: newtype State s a = State { runState :: s -> (a, s) }. 提示: 或许练习2会很有用.)
[2,7,8] *> [3,9] 的结果是什么? (在动手前先猜一下.)
使用其它 Applicative 实现 (<**>).
正如我们所见, 有些 functor 可以有两种副作用序列化方向不同的 (<*>) 实现. 为什么 (>>=) 没有这个问题呢?

兵器谱

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, (<*>) 和 (=<<) 的陪域 (或称目标, codomain) 都是 {域 (或称源, domain) 和陪域都是 Functor 的函数} ^[1]. 它们的差异之处在于域的不同:

fmap 的域是任意函数.
(<*>) 的域是形如 t (a -> b) 的函数.
(=<<) 的域是形如 a -> t b 的函数.

Functor, Applicative 和 Monad 的本质不同在于它们的类型赋予我们的能力. 从 fmap 到 (<*>) 再到 (>>=), 我们对于值的控制力和计算的灵活性逐渐增加, 但这是以结果性质的弱化为代价的. 我们将逐条浏览这个 "Haskell 兵器谱". 下文中, 我们分别使用值和额外信息来指代这些 Functor 中包裹的值和除了这个值以外其携带的信息.

fmap 的类型保证了不管用什么函数我们都无法改变值的额外信息. 在 (a -> b) -> t a -> t b 这个类型中, (a -> b) 函数和 t a 的额外信息 t (某种意义上, 非正式地, 我们用 t 表示 t a 的额外信息) 完全没有联系, 因此这个函数无法对额外信息造成任何影响. 由此可得, 操作列表 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 结合的 t (a -> b) 自带了一个额外的信息. (<*>) 有着一个更微妙的限制. 尽管 t (a -> b) 本身携带了额外信息, 在其中的函数 (a -> b) 仍然不能改变外界 Applicative 的额外信息. 这意味着, (<*>) 对额外信息的改动仅仅是由额外信息本身所决定的, 在 Applicative 中的值不能对这个改动造成任何影响.

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 的 (<*>), 我们知道, 和真实世界的交互将在运算完毕后发生^[2], 以此类推.

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 "太小了" else "没问题"
"太小了"
Prelude> return 42 >>= \x -> print $ if x < 10 then "太小了" else "没问题"
"没问题"

然而, 在获得这些灵活性的同时, 我们也弱化了许多计算结果的有用性质; 例如, 对于异常输入, 函数不再保证总是保留值中的额外信息; 程序的控制流或许会变得更加难以分析. 在某些情况下, 由于 Monad 带来了对之前计算结果的依赖, 一些自动重构优化被禁用, 程序性能也会受到影响. ^[3] 总之, 为我们要解决的问题选择一个灵活性匹配而不是超过或者不足的抽象通常是个好主意. 如果我们会用到 Monad 的额外能力, 选择它或许是个好主意; 然而, 或许我们也应该想想 Applicative 或 Functor 是否已经足以满足我们的需求.

练习

以下练习中我们用到这个数据结构:
data AT a = L a | B (AT a) (AT a)

为 AT 实现 Functor, Applicative 和 Monad 的 instance. 不要使用诸如 pure = return 这样的偷懒写法. Applicative 和 Monad 的 instance 应该相互匹配; 注意, (<*>) 应该和 ap 等价, 虽然后者是由 Monad instance 衍生出来的.
使用 Applicative 或 Monad 实现下列函数; 若它们都无法提供相应的能力, 就两个都不用. 若 Applicative 和 Monad 都能够完成任务, 选择能力最小的那一个. 简要说明你选择的理由.
a. fructify :: AT a -> AT a, 其将树中的所有叶子替换成一个左右子树都等于该叶子的分枝.
b. prune :: a -> (a -> Bool) -> AT a -> AT a, prune z p t 表示, 若 t 左右子树中的某一个是叶子, 且满足 p 时, 将 t 替换成 L z.
c. reproduce :: (a -> b) -> (a -> b) -> AT a -> AT b, reproduce f g t 返回一棵根节点的左右子树分别为将 f 和 g 应用到 t 得到的值的树.
AT 可以有另一个 Applicative instance (不是指将副作用反向的版本). 试着实现它. 提示: 这个版本能够用来实现:
sagittalMap :: (a -> b) -> (a -> b) -> AT a -> AT b
若其参数是一个分枝, 则将两个函数分别应用到它的左右子树上去.

(你或许会感兴趣, "AT" 表示 "apple tree (苹果树)". 若读者们是植物学家, 还请谅解这个糟糕的隐喻.)

`Applicative` 的 monoid 形式

我们已经知道, 除了 (>>=), Monad 也能够用 (>=>) 或 join 定义. 类似的, Applicative 也有着替代的表示:

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

之所以叫做 "monoid 形式" 是由于背后的一些理论原因 ^[4]. 非正式地, 我们可以认为它看起来和 monoid 有些相似: unit 提供了一个默认的 functor 中的值, 其额外信息只是个占位符, 不包含任何有用的信息; (*&*) 将 functor 中的值合并成一个二元组并将额外信息合并. Monoidal 的结构向我们更清楚地展示了 Applicative 是如何操作额外信息的. 自然, unit 和 (*&*) 能够被用来定义 pure 和 (<*>), 反之既然.

Applicative 法则和下列 Monoidal 法则等价:

fmap snd $ unit *&* v = v                    -- 左单位元
fmap fst $ u *&* unit = u                    -- 右单位元
fmap asl $ u *&* (v *&* w) = (u *&* v) *&* w -- 结合律
-- asl (x, (y, z)) = ((x, y), z)

($) 左边函数的作用只是在等价的类型之间进行转换, 例如 b 和 ((), b). 如果我们忽视这种转换, 这些法则就比 Applicative 的形式更加清晰了. 顺便一提, 如同 Applicative 一样, 有一条保证成立的额外推论.

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

练习
使用 `pure` 和 `(<>)` 实现 `unit` 和 `(&*)`, 反过来也做一遍. 使用 `Monoidal` 的函数描述满足交换律的 Applicative. 为以下类型实现 `Monoidal` instance: a. `ZipList` b. `((->) r)`