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)