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