Haskell/Applicative類型類
此處只翻譯了一些其它教程 (主要指 《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
, 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
是否已經足以滿足我們的需求.
練習 |
---|
以下練習中我們用到這個數據結構:
|
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)
練習 |
---|
|
Applicative類型類 |
習題解答 |
高級Haskell |
Monoid類型類 >> Applicative類型類 >> 箭頭 >> 理解箭頭 >> Foldable類型類 >> Traversable類型類 >> 延續過渡風格(CPS) >> 可變對象 >> 拉鏈 >> 適用函子 >> 獨異點 >> Lens 和引用 >> 並行 |
Haskell |
Haskell基礎
>> 初級Haskell
>> Haskell進階
>> Monads
|
- ↑ 這裡類型簽名表面上的相似有着更深的理論意義. 其中之一就是, 這三個類型類都有着恆等法則 (identity law) 和結合律法則並不是偶然.
- ↑ 譯註: 事實上,
IO
遠比這裡描述的要複雜得多 (或者說, "運用了許多黑魔法"). 對本句有疑問的讀者請不用深究. - ↑ 例如 [1] 中的腳註.
- ↑ 請參見 Typeclasseopedia 中的相應資料以及Edward Z. Yang 的博客.