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