8 min to read
CIS 194 09 Functors 函子
Source: 09-functors
▌Functors 函子
CIS 194 第 9 週 2013 年 3 月 18 日
建議閱讀：
- Learn You a Haskell, The Functor typeclass
- The Typeclassopedia
▌Motivation 動機
在過去的幾周中，我們看到了許多旨在將函數“映射”到某種容器的每個元素上的函數。例如：
map :: (a -> b) -> [a] -> [b]
treeMap :: (a -> b) -> Tree a -> Tree b
在作業 5 中，當您不得不以某種方式將 Maya ExprT 應用於 eval :: ExprT -> Int 以獲得 Maybe Int 時，許多人做了類似的東西
maybeEval :: (ExprT -> Int) -> Maybe ExprT -> Maybe Int
maybeMap :: (a -> b) -> Maybe a -> Maybe b
這裡有一個重複的模式，作為優秀的 Haskell 程序員，我們想知道如何概括它！那麼哪些部分在示例之間相同，哪些部分不同？
當然，不同的部分是容器被 “映射”：
thingMap :: (a -> b) -> f a -> f b
但是這些“容器”是什麼東西？ 我們真的可以像 f 一樣給它們分配一個的類型變量嗎？
▌A brief digression on kinds 關於種類的簡要論述
正如每一個表達式都有一個類型，類型本身有 “類 (types)” 叫 種 (kinds)。（在您問之前：不，除了種類，沒有別的層次 —— 至少在 Haskell 中沒有）在 ghci 可以使用 :kind 詢問類型的種類。例如，讓我們問一下Int：
Prelude> :k Int
Int :: *
我們看到這 Int 有 *。實際上可以用作某些值的類型的每個類型都具有 *
Prelude> :k Bool
Bool :: *
Prelude> :k Char
Char :: *
Prelude> :k Maybe Int
Maybe Int :: *
如果 Maybe Int 的種類為 * ，那麼 Maybe 呢？ 請注意，沒有 Maybe 類型的值。 有類型 Maybe Int 和 Maybe Bool 類型的值，但沒有 Maybe 類型的值。 但 Maybe 肯定是一個有效的類。 所以那是什麼？它有什麼種類？ 讓我們問一下 ghci：
Prelude> :k Maybe
Maybe :: * -> *
ghci 告訴我們 Maybe 有 * -> * 。 Maybe 從某種意義上說，它是 類型 上的函數 —— 我們通常將其稱為類型構造函數 (type constructor) 。Maybe 接受一種類型的輸入類型 *，並產生另一種類型的類型 *。例如，它可以作為輸入 Int :: * 並產生新的類型 Maybe Int :: *
是否還有其他帶有 * -> * 的類型構造函數？當然，例如 Tree 或列表類型構造函數，如 []
Prelude> :k []
[] :: * -> *
Prelude :k [] Int
[] Int :: *
Prelude> :k [Int] -- special syntax for [] Int
[Int] :: *
Prelude> :k Tree
Tree :: * -> *
那麼其他類型的構造函數呢？ 作業 7 中的 JoinList 怎樣？
data JoinList m a = Empty
| Single m a
| Append m (JoinList m a) (JoinList m a)
Prelude> :k JoinList
JoinList :: * -> * -> *
這是有道理的：JoinList 期望兩種 類型用作參數，並為我們提供新的類型（當然，它是柯里化 (curried) 的，因此我們也可以將其視為接受 一種 類型並返回某種類型 * -> * ）這是另一種：
Prelude> :k (->)
(->) :: * -> * -> *
這告訴我們函數類型構造函數帶有兩個類型參數。像任何運算符一樣，我們用中綴 (infix)：
Prelude> :k Int -> Char
Int -> Char :: *
但是我們不必：
Prelude> :k (->) Int Char
(->) Int Char :: *
好，那這個呢？
data Funny f a = Funny a (f a)
Prelude> :k Funny
Funny :: (* -> *) -> * -> *
Funny 接受兩個參數，第一個是類型 * -> * ，第二個是類型 *，並構造一個類型。 （ GHCi 是怎麼知道 Funny 類型的呢？好吧，它也進行推斷，就像它也進行類型推斷一樣） Funny 是一個高階類型構造函數，就像 map 是一個高階函數一樣。 請注意，類型也可以像函數一樣部分地應用：
Prelude> :k Funny Maybe
Funny Maybe :: * -> *
Prelude> :k Funny Maybe Int
Funny Maybe Int :: *
▌Functor 函子
我們看到的映射模式的本質是一個具有如下類型的高階函數
thingMap :: (a -> b) -> f a -> f b
其中 f 是代表某種類型 * -> * 的類型變量。 那麼，我們可以一勞永逸地編寫此類函數嗎？
thingMap :: (a -> b) -> f a -> f b
thingMap h fa = ???
好吧，並不是的。如果我們不知道 f 是什麼，我們將無能為力。 對於每個特定的 f，thingMap 必須以不同的方式工作。 解決方案是創建一個類型類，傳統上稱為 Functor：
class Functor f where
fmap :: (a -> b) -> f a -> f b
（Functor 在標準 Prelude 中定義。請注意，“ functor” 的名稱來自範疇論，與 C++ 中的函子（本質上是頭等 (first-class) 函數）不同）現在，我們可以以特定於每個特定 f 的方式實現此類。 注意，Functor 是對 * -> * 類型進行抽象。 所以下面這樣寫來沒有意義：
instance Functor Int where
fmap = ...
如果我們嘗試一下，我們會得到一個非常好的 種類不匹配錯誤 ：
[1 of 1] Compiling Main ( 09-functors.lhs, interpreted )
09-functors.lhs:145:19:
Kind mis-match
The first argument of `Functor' should have kind `* -> *',
but `Int' has kind `*'
In the instance declaration for `Functor Int'
如果我們了解種類，則該錯誤會告訴我們確切的錯誤所在
但是，為 Maybe 創建一個 Functor 實例確實是有意義的。 我們開始做吧。 遵循類型使其變得微不足道：
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap h (Just a) = Just (h a)
列表呢？
instance Functor [] where
fmap _ [] = []
fmap f (x:xs) = f x : fmap f xs
-- or just
-- fmap = map
十分簡單。那 IO 呢？為 IO 創建 Functor 實例是否有意義？
當然。fmap :: (a -> b) -> IO a -> IO b 導致 IO 操作，該 IO a 操作首先運行該操作，然後在返回結果之前應用該函數轉換結果。我們可以輕鬆實現此目標：
instance Functor IO where
fmap f ioa = ioa >>= (\a -> return (f a))
或甚至
instance Functor IO where
fmap f ioa = ioa >>= (return . f)
現在讓我們嘗試一些令人費解的事情：
instance Functor ((->) e) where
什麼！？好吧，讓我們按照以下類型：如果 f = (->) e 那麼我們想要
fmap :: (a -> b) -> (->) e a -> (->) e b
或者，用 (->) 書面中綴：
fmap :: (a -> b) -> (e -> a) -> (e -> b)
嗯，這種類型的簽名似乎很熟悉 ……
instance Functor ((->) e) where
fmap = (.)
瘋！這是什麼意思？好吧，一種考慮類型值的方法 (e -> a) 是將其作為一個 “e 索引容器” ， 其中每個 e 值都有一個 a 值。 要在這樣一個容器中的每個值上映射一個函數，就完全對應於函數組成：從轉換後的容器中選擇一個元素，我們首先應用 (e -> a) 函數從原始容器中選擇一個 a，然後 然後應用 (a -> b) 函數來變換我們選擇的元素
