Functor 與 Applicative_Haskell 筆記 7

一.Functor 像盒子？

盒子的比喻

常見的 Functor 類實例似乎都可以比作盒子（或者叫容器），比如 Maybe/Either，List（[]）：

> fmap (+1) (Just 3)
Just 4
> fmap (+1) (Right 3)
Right 4
> fmap (+1) [1, 2, 3]
[2,3,4]

通過 fmap 把函數作用於容器裡的值，得到一個裝著新值的同類容器，甚至 I/O Action 也可以這樣理解：

> fmap (++"!") getLine
abc
"abc!"

I/O Action 類容器特殊之處在於，容器裡的值是不確定的，取決於外部輸入，可能來自用戶鍵入、文件讀取、甚至直接從系統環境取（比如隨機數種子）。但可以肯定的是，I/O Action 這個容器裡裝著一個值（不論這個值來自哪裡），而 fmap 能夠把函數作用於這個值，同樣得到一個裝著新值的 I/O Action

至此，盒子的比喻仍然很恰當：純環境下的容器是木質寶箱，裡面裝著確定不變的東西，而不純環境下的容器是食人寶箱，裡面不知道裝著個啥。如下圖（六一剛過，調皮一下）：

[caption id="attachment_1722" align="alignnone" width="423"] functor and box[/caption]

函數也是 Functor 類實例？！

那麼，是不是所有的 Functor 類實例都可以這樣理解呢？

instance Functor (Const m) -- Defined in 'Data.Functor.Const'
instance Functor (Either a) -- Defined in 'Data.Either'
instance Functor [] -- Defined in 'GHC.Base'
instance Functor Maybe -- Defined in 'GHC.Base'
instance Functor IO -- Defined in 'GHC.Base'
instance Functor ((->) r) -- Defined in 'GHC.Base'
instance Functor ((,) a) -- Defined in 'GHC.Base'

（注意：簡單起見，上面列出的只是一般 Functor 實例，去掉了 3 個同樣屬於 Applicative 的特殊 Functor 實例）

其它幾個都沒什麼特別的，((->) r) 這個東西長得有點奇怪，看起來像函數定義（r map to something），看下定義：

instance Functor ((->) r) where
  fmap = (.)

((->) r) 確實是 Functor 類實例，實現的 fmap 就是函數組合（.）：

(.) :: (b -> c) -> (a -> b) -> a -> c

接受一個 map b to c 的函數和一個 map a to b 的函數，把後者的輸出連接到前者的輸入，返回 map a to c 的函數。這是我們所熟知的函數組合，但又與 Functor 有什麼關係？

首先 Functor 的 fmap 類型是：

fmap :: Functor f => (a -> b) -> f a -> f b

既然 ((->) r) 也是 Functor 實例，用 ((->) r) 換掉 f：

fmap :: (a -> b) -> (->) r a -> (->) r b

最後把 -> 換成習慣的中綴形式：

fmap :: (a -> b) -> (r -> a) -> (r -> b)

這，不就是函數組合（.）嗎？

(.) :: (b -> c) -> (a -> b) -> a -> c

所以，函數也是 Functor 類實例

P.S.那麼，((->) r) 為什麼長得這麼奇怪？因為 Functor class 要求：

class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b

f 必須是接受一個具體類型參數的類型（* -> *），而 -> 是：

(->) :: * -> * -> *

多了個參數，所以先填一個，就得到醜醜的 (->) r 了（r 只是個形參名，叫 a 叫 b 都行）

更恰當的比喻

函數，確實很難被想成是盒子。想像力實在豐富的話，可以想作生化盒子（魔斯拉），或者坩堝（女巫森林一張新卡）之類的能讓內容發生變化的盒子，嗯，試管

函數層面的 fmap 就是函數組合，對著 map a to b 的函數，做一發 map b to c 的映射，得到一個 map a to c 的新函數：

instance Functor ((->) r) where
  fmap = (.)

(.) :: (b -> c) -> (a -> b) -> a -> c

對比之前盒子的比喻：

通過 fmap 把函數作用於容器裡的值，得到一個裝著新值的同類容器

代入我們發明的生化盒子，得到：通過 fmap 把（生化）盒子作用於（生化）盒子，得到一個新（生化）盒子

這 3 個「（生化）盒子」要怎麼理解？

把 map a to b 和 map b to c 當做兩根試管，並且如果試管能連接的話，勉強說得通：

-- 試管 ab 能把水變紅
a -> b
-- 試管 bc 能把紅水變藍
b -> c
-- 拿試管 bc 對 ab 做映射，就是把 ab 的底戳個洞，套進 bc 試管
(b -> c) . (a -> b)
-- 得到一根（更長的）新試管 ac，作用是把水變藍
a -> c

為什麼比作試管（或者生化盒子）？因為代指一種轉換，想要表達變化。而我們所理解的盒子，缺少這種具有轉換作用的含義，因此這個比喻不恰當

所以，對於函數上下文的 Functor

盒子的比喻不是那麼恰當，functors 其實比較像 computation。function 被 map over 到一個 computation 會產生經由那個 function 映射過後的 computation

上面這個描述相當貼切了，computation 就是數據轉換，而轉換是能做映射的，做映射的方式就是組合

一個比較正確的形容是 functors 是一個計算語境（computational context）。這個語境可能是這個 computation 可能帶有值，或是有可能會失敗（像 Maybe 跟 Either a），或是他可能有多個值（像 lists），等等。

所以，別叫盒子了，叫計算語境，fmap 相當於對這個計算語境追加一層轉換（做映射）

Lifting

再看一遍 fmap 的類型定義：

fmap :: Functor f => (a -> b) -> f a -> f b

輸入一個 map a to b 的函數和一個 Functor 實例 a，返回另一個 Functor 實例 b，沒什麼特別的

換個姿勢再看：

fmap :: Functor f => (a -> b) -> (f a -> f b)

輸入一個 map a to b 的函數，返回另一個函數，這個函數的作用也是 map a to b，但處於 Functor 的語境裡（參數和返回值都被包進了 Functor 裡），好像有那麼點意思了

把一個函數轉換為另一個環境下的對應函數，稱為 lifting（提升？沒發現合適的翻譯）：

Lifting is a concept which allows you to transform a function into a corresponding function within another (usually more general) setting.

看這個例子：

> replicate 3 'a'
"aaa"
> :t replicate
replicate :: Int -> a -> [a]
> :t liftA2 replicate
liftA2 replicate :: (Applicative f) => f Int -> f a -> f [a]
> (liftA2 replicate) [1,2,3] ['a','b','c']
["a","b","c","aa","bb","cc","aaa","bbb","ccc"]
> :t liftA2
liftA2 :: (Applicative f) => (a -> b -> c) -> (f a -> f b -> f c)

其中 liftA2 所做的事情就是 lifting，根據一個普通函數（replicate）製造一個功能類似的新函數，新的能夠應用於另一個環境（Applicative 上下文）：

--  普通函數
Int -> a -> [a]
--  lift 一下
f Int -> f a -> f [a]

所以，lift 就是方便讓普通函數能夠在 f 的語境裡正常工作

P.S.類似的 lift 函數共有 3 個：

liftA :: Applicative f => (a -> b) -> f a -> f b
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d

更多參數的可以通過 <$> 和 <*> 秒秒鐘定義出來，見下面 Applicative instances 小節的 (->) r 部分

二.Functor laws

之前有提到：

實現 Functor 時需要遵循一些規則，比如不希望 List 元素順序發生變化，希望二叉搜索樹仍保留其結構性質等等

（摘自 [深入 typeclass_Haskell 筆記 4](/articles/深入 typeclass-haskell 筆記 4/)）

所以 functor laws 的作用就是約束 fmap，讓映射結果保持一些性質：

如果遵守了 functor laws，我們知道對它做 fmap 不會做多餘的事情，只是用一個函數做映射而已

一共 2 條規則：

fmap id = id
fmap (f . g) = fmap f . fmap g

P.S.第二條也可以寫作 fmap (f . g) F = fmap f (fmap g F)，去掉組合更容易理解一些

第一條，如果我們對 functor 做 map id，那麼得到的新 functor 應該與原來的完全一樣

第二條，將兩個函數組合起來並將結果 map over 一個 functor 的結果，應該跟先將第一個函數 map over 一個 functor，再將第二個函數 map over 第一步得到的 functor 的結果完全一樣

（內置的）Functor 類實例都滿足這兩條規則，例如：

> fmap id (Just 3)
Just 3
> fmap id Nothing
Nothing
> fmap ((+1) . (*2)) (Just 3)
Just 7
> fmap (+1) . fmap (*2) $ Just 3
Just 7

但手動實現的 Functor 實例就不一定了，因為這兩條規則只是道德約束，沒有強檢查，所以在實現自定義 Functor 實例時應該注意自覺遵守

三.Applicative functors

看名字叫加強版的 Functor，那麼強在哪裡？

我們知道 Functor 圈定了一類能被 map over 的東西，可以對著 Functor 實例用 fmap，把普通函數作用於 Functor 的計算語境

似乎足夠強大了，但有些特殊場景，例如：

> :t fmap (+) (Just 3)
fmap (+) (Just 3) :: Num a => Maybe (a -> a)

這是個什麼東西？Maybe 裡裝了個函數（即 Just (+3)），那這個函數要怎麼拿出來用呢？

比如想作用於 Just 2 的話，我們這樣做：

> let (Just f) = (Just (+3)) in fmap f (Just 2)
Just 5

先模式匹配取出 (+3)，再對 Just 2 做 (+3) 映射，因為我們無法單純用 fmap 把包在一個 Functor 裡的函數作用於另一個包在 Functor 裡的值上

那麼有沒有一種對任何 Functor 都有效的通用模式，能幫助我們完成這個事情（把一個 Functor 裡的函數作用於另一個 Functor 裡的值）？

有。這個東西就是 Applicative：

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

（摘自 Applicative）

要求必須先是 Functor 實例，所以 Applicative 是一種特殊的 Functor，所以也被稱為 Applicative functors

定義了兩個接口 pure 與 <*>

pure 把一個普通值放到一個缺省的 context 下，一個最小的 context 但仍然包含這個值

怎麼理解？看示例：

> pure 1 :: [Int]
[1]
> pure 1 :: Maybe Int
Just 1
> pure 1 :: IO Int
1

對於 List 而言，最小的 context 就是 []（空 List），所以把 1 放進來得到 [1]。Maybe 的話，Nothing 沒有儲值的能力，context 只能是 Just，所以是 Just 1。I/O Action 的話，當然是 return 1（通過 return 把值放進 I/O Action 裡）

<*> 的作用是：

It applies the wrapped function to the wrapped value

這正是我們想要的，把一個 Functor 裡的函數作用於另一個 Functor 裡的值

所以，Applicative 對 Functor 的增強體現在 <*> 函數上，增強方式是讓這些 Functor 實例都實現個 <*>，支持把一個 Functor 裡的函數作用於另一個 Functor 裡的值

帶來 2 個好處，其一是對多參函數更友好：

如果只是普通的 functor 的話，我們只能將一個（單參）函數 map over 這個 functor。但有了 applicative functor，我們可以對好多個 functor 套用一個（多參）函數

其二是允許 Functor 結合（而不像 fmap 算一次得到個 Functor 就只能結束了，通過 <*> 能夠繼續運算下去）：

applicative functor 不只是有趣而且實用，它允許我們結合不同種類的計算，像是 I/O 計算，non-deterministic 的計算，有可能失敗的計算等等。而使用 <$> 跟 <*> 我們可以將普通的函數來運作在任意數量的 applicative functors 上。

例如：

> (+) <$> (Just 1) <*> (Just 2)
Just 3
> (\a b c -> a + b + c) <$> (Just 1) <*> (Just 2) <*> (Just 3)
Just 6
> (+3) <$> ((+) <$> (Just 1) <*> (Just 2))
Just 6

四.Applicative instances

Applicative 類有很多實例：

instance Monoid m => Applicative (Const m)
  -- Defined in 'Data.Functor.Const'
instance Applicative (Either e) -- Defined in 'Data.Either'
instance Applicative ZipList -- Defined in 'Control.Applicative'
instance Monad m => Applicative (WrappedMonad m)
  -- Defined in 'Control.Applicative'
instance Control.Arrow.Arrow a => Applicative (WrappedArrow a b)
  -- Defined in 'Control.Applicative'
instance Applicative [] -- Defined in 'GHC.Base'
instance Applicative Maybe -- Defined in 'GHC.Base'
instance Applicative IO -- Defined in 'GHC.Base'
instance Applicative ((->) a) -- Defined in 'GHC.Base'
instance Monoid a => Applicative ((,) a) -- Defined in 'GHC.Base'

Maybe

instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  (Just f) <*> something = fmap f something

對 Maybe 類型而言，最小的能讓值參與運算的 context 就是 Just something，從 Nothing 中取不出函數，所以結果一定是 Nothing，如果左側不是 Nothing，就模式匹配從中取出函數 f，並通過 fmap 作用於右側的 Maybe 實例（something）

List

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

pure f 就是 [f]，而 [f] <*> xs 將左邊的每個函數套用至右邊的每個值

P.S.很容易發現 pure f <*> xs 其實等價於 fmap f xs，這也是 Applicative laws 其中一條

IO

instance Applicative IO where
  pure = return
  a <*> b = do
    f <- a
    x <- b
    return (f x)

pure 的對應實現就是 return，把一個值包進 I/O Action，讓它能夠參與 IO 運算，<*> 所做的事情就是分別從左右兩側的 I/O Action 裡取出函數和值，做完運算再用 return 包好結果

(->) r

instance Applicative ((->) r) where
  pure x = (\_ -> x)
  f <*> g = \x -> f x (g x)

這個看起來有些奇怪，pure 生成一個返回常量的函數，<*> 把左右兩側的函數組合起來

例如：

(+) <$> (+3) <*> (*100)

其中*<$> 就是中綴版的 fmap*，如下：

infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

<*> 與 <$> 都是 infixl 4（中綴左結合，優先級為 4），所以展開過程是這樣：

(+) <$> (+3) <*> (*100)
=(fmap (+) (+3)) <*> (*100)
=((.) (+) (+3)) <*> (*100)
=((+) . (+3)) <*> (*100)
=\x -> ((+) . (+3)) x ((*100) x)
=\x -> (+) ((+3) x) ((*100) x)

即：

f1 <$> f2 <*> f3
=\x -> f1 (f2 x) (f3 x)

將兩個 applicative functor 餵給 <*> 可以產生一個新的 applicative functor，所以如果我們丟給他兩個函數，我們能得到一個新的函數

所以 f1 <$> f2 <*> f3 的實際效果是：製造一個把 f2 和 f3 的結果作為參數調用 f1 的函數。那麼就有：

f1 <$> f2 <*> f3 <*> ... <*> fn
=\x -> f1 (f2 x) (f3 x) ... (fn x)

P.S.f1 <$> f2 <*> f3 這種固定模式有個工具函數，叫 liftA2：

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = f <$> a <*> b

liftA2 接受一個普通的二元函數，並將他升級成一個函數可以運作在兩個 functor 之上

這就是所謂的 lifting（升級？）

ZipList

對比 List：

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

ZipList 的實現如下：

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

P.S.ZipList 位於 Control.Applicative 模塊，之所以存在 ZipList，是因為無法再賦予 List 另一種不同的 Applicative 實現

pure 實際上生成了一個無限長的 ZipList，這是因為 zipWith 結果以兩個 List 中較短的那個為準，所以，為了保證 x 能正常參與運算（滿足另一側任意長度的 List），所以對於 ZipList 而言，ZipList (repeat x) 就是最小的那個 context

<*> 是從左側取出函數 List，從右側取出數據 List，再對兩個 List 的元素一一結對做映射（zipWith）

讓左側函數 List 裡只有同一個函數的話，就相當於拿這個函數對右側 List 做映射：

> getZipList $ pure (+1) <*> (ZipList [1, 2, 3])
[2,3,4]

P.S.其中 getZipList :: ZipList a -> [a] 是個 getter（具體見 [類型_Haskell 筆記 3 | Record](/articles/類型-haskell 筆記 3/#articleHeader8)），用來取出裡面的 List

換個花樣：

> getZipList $ (+) <$> ZipList [1, 2, 3] <*> (ZipList [1, 2, 3])
[2,4,6]
> getZipList $ max <$> ZipList [1, 3, 4, 5] <*> ZipList [2, 0]
[2,3]

五.Applicative laws

同樣，Applicative 也要遵循一些規則：

pure f <*> x = fmap f x
pure id <*> v = v
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u

通過 pure 讓普通函數 f 能夠參與 Functor 運算，��以有：

pure f <*> x = fmap f x
pure id <*> v = v
pure f <*> pure x = pure (f x)

通過 <*> 讓左側 Functor 中的函數能夠作用於右側 Functor 中的值，所以：

-- $ 固定參數位置
u <*> pure y = pure ($ y) <*> u
-- (.) 改變結合性
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

內置的 Applicative 實例都遵從這些規則，但同樣只是道德約束，手動實現 Applicative 實例時要自覺遵守

Applicative style

通過 <$> 和 <*> 可以達到非常優雅的調用式風格。例如：

> (++) <$> Just "johntra" <*> Just "volta"
Just "johntravolta"

類比函數調用：

> (++) "johntra" "volta"
"johntravolta"

在 I/O 場景更明顯：

myAction = do
  a <- getLine
  b <- getLine
  return $ a ++ b

對應的 applicative style：

myAction = (++) <$> getLine <*> getLine

相當優雅，讓 Functor 層面的運算與普通運算在形式上幾乎沒什麼差異了（從形式上消除了運算所處 context 的差異）