Applicative類型類 (解答)

## ZipList

(<*>) :: [a -> b] -> [a] -> [b]

... 也就是說, (<*>) 將一列表的函數應用到另一個列表上, 但詳細情況是怎樣的呢?

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

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

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

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

pure id <*> v = v

(<*>) 展開, 並假定我們使用上面的 pure 實現, 我們得到:

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

ZipList (zipWith (\$) [id] [1..]) = ZipList [1..]
ZipList [1] = ZipList [1..]
[1] = [1..] -- 显然不等!

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

>>> 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)]}

## 副作用序列化

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

--- ...

[8,10,12,15]

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

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

(*>) :: 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

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

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

newtype Backwards f a = Backwards { forwards :: f a }
>>> Backwards [(2*),(3*)] <*> Backwards [4,5]
Backwards [8,12,10,15]

1. 為列表 functor 實現 (<*>) 和它的"副作用倒置版本"
(<|*|>) :: Applicative f => f (a -> b) -> f a -> f b, 且不使用任何來自 Applicative 或者 Monad 的函數.
2. 使用 do 代碼塊重寫 Monad 的交換律, 不使用 apliftM2.
3. 以下的 Applicative 滿足交換律嗎?
a. ZipList
b. ((->) r)
c. State s (使用這個定義: newtype State s a = State { runState :: s -> (a, s) }. 提示: 或許練習2會很有用.)
4. [2,7,8] *> [3,9] 的結果是什麼? (在動手前先猜一下.)
5. 使用其它 Applicative 實現 (<**>).
6. 正如我們所見, 有些 functor 可以有兩種副作用序列化方向不同的 (<*>) 實現. 為什麼 (>>=) 沒有這個問題呢?

## 兵器譜

Functor, Applicative, Monad. 它們是緊密相連的, 同時也是 Haskell 中最重要的三個類型類. 雖然我們已經見過實際使用中 FunctorMonad 的許多例子, 甚至還見過一些 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

(<\$>) :: 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 的域是任意函數.
• (<*>) 的域是形如 t (a -> b) 的函數.
• (=<<) 的域是形如 a -> t b 的函數.

Functor, ApplicativeMonad 的本質不同在於它們的類型賦予我們的能力. 從 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

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 "没问题"
"没问题"

data AT a = L a | B (AT a) (AT a)

1. AT 實現 Functor, ApplicativeMonad 的 instance. 不要使用諸如 pure = return 這樣的偷懶寫法. ApplicativeMonad 的 instance 應該相互匹配; 注意, (<*>) 應該和 ap 等價, 雖然後者是由 Monad instance 衍生出來的.
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 返回一棵根節點的左右子樹分別為將 fg 應用到 t 得到的值的樹.
3. AT 可以有另一個 Applicative instance (不是指將副作用反向的版本). 試着實現它. 提示: 這個版本能夠用來實現:
sagittalMap :: (a -> b) -> (a -> b) -> AT a -> AT b
若其參數是一個分枝, 則將兩個函數分別應用到它的左右子樹上去.
(你或許會感興趣, "AT" 表示 "apple tree (蘋果樹)". 若讀者們是植物學家, 還請諒解這個糟糕的隱喻.)

## Applicative 的 monoid 形式

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

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)

1. 使用 pure(<*>) 實現 unit(*&*), 反過來也做一遍.
2. 使用 Monoidal 的函數描述滿足交換律的 Applicative.
3. 為以下類型實現 Monoidal instance:
a. ZipList
b. ((->) r)

 Applicative類型類 習題解答 高級Haskell Monoid類型類  >> Applicative類型類  >> 箭頭  >> 理解箭頭  >> Foldable類型類  >> Traversable類型類  >> 延續過渡風格（CPS）  >> 可變對象  >> 拉鏈  >> 適用函子  >> 獨異點  >> Lens 和引用  >> 並行 編輯此章節 Haskell 庫參考 >> 普通實務 >> 特殊任務 編輯書目結構
1. 這裏類型簽名表面上的相似有着更深的理論意義. 其中之一就是, 這三個類型類都有着恆等法則 (identity law) 和結合律法則並不是偶然.
2. 譯註: 事實上, IO 遠比這裏描述的要複雜得多 (或者說, "運用了許多黑魔法"). 對本句有疑問的讀者請不用深究.
3. 例如 [1] 中的腳註.