Bifunctor
ってなんだよ、っていうと型引数を2つとるFunctor
の兄弟です。語源はbi-functorという造語だと思われます。*bi-*は2つの、とか共通の、という意味があるので「双関手」と訳します。
定義
class Bifunctor p where
bimap :: (a -> b) -> (c -> d) -> p a c -> p b d
bimap f g = first f . second g
first :: (a -> b) -> p a c -> p b c
first f = bimap f id
second :: (b -> c) -> p a b -> p a c
second = bimap id
型をBifunctor
のインスタンスにしたければ、bimap
かfirst
とsecond
を実装せよ、とあります。first
とsecond
、bimap
はお互いを呼び出しあっています。
bimap
はfmap
と同じく包まれた値に関数を適用するのですが、p
が型を2つ持っているのに気づきましたか? そうです。Bifunctor
は値を2つつつむFunctor
なのです。
遊んでみる
Bifunctor
を使うにはData.Bifunctor
をインポートします。
Prelude> :m Data.Bifunctor
Prelude Data.Bifunctor>
Bifunctor
のインスタンスはいくつかありますが、なじみ深いのはEither
かと思われます。
instance Bifunctor Either where
bimap f _ (Left a) = Left (f a)
bimap _ g (Right b) = Right (g b)
Left
でも値がスルーされずに、ちゃんと関数が適用されてくれます。
Prelude Data.Bifunctor> bimap (+5) length $ Right [1,2,3]
Right 3
Prelude Data.Bifunctor> bimap (+5) length $ Left 10
Left 15
Bifunctorのルール
型をインスタンスにする際に守らなければならないルールがいくつかあります。
1. bimap id id = id
2. first id = id
3. second id = id
4. bimap f g = first f . second g
上の3つは値が保存されること、4つ目は関数合成についてのルールです。
インスタンスたち
タプル
instance Bifunctor (,) where
bimap f g ~(a, b) = (f a, g b)
標準ライブラリでは5タプルまでがインスタンスとして実装されています。全て最後の2つの要素に関数が適用されます。
Prelude Data.Bifunctor> bimap (+2) (+10) (1,2)
(3,12)
Prelude Data.Bifunctor> bimap (++" world") (^2) ("hello", 10)
("hello world",100)
ルールを満たしていることを証明します。
1. bimap id id (a,b)
= (id a, id b)
= (a, b)
= id (a, b)
2. first id (a,b)
= (id a, b)
= (a, b)
= id (a, b)
3. second id (a,b)
= (a, id b)
= (a, b)
= id (a, b)
4. bimap f g (a,b)
= (f a, g b)
= first f (a, g b)
= first f (second g (a, b))
= (first f . second g) (a, b)
もちろん、ペア以外のタプルでも同様に証明できます。
Either
instance Bifunctor Either where
bimap f _ (Left a) = Left (f a)
bimap _ g (Right b) = Right (g b)
挙動は先程説明したとおり、Left
かRight
かに関わらず関数は適用されます。ルールを証明してみます。
1. bimap id id (Either a b)
= Either (id a) (id b)
= Either a b
= id (Either a b)
2. first id (Either a b)
= Either (id a) b
= Either a b
= id (Either a b)
3. second id (Either a b)
= Either a (id b)
= Either a b
= id (Either a b)
4. bimap f g (Either a b)
= Either (f a) (g b)
= first f (Either a (g b))
= first f ((second g (Either a b)))
= (first f . second g) (Either a b)
Const
Const
については別の記事にまとめます。
K1
再帰カインドと関係があるようですが、情報が少なくまとめられませんでした。1
Bifunctorの法則
bimap (f . g) (h . i) = bimap f h . bimap g i
first (f . g) = first f . first g
second (f . g) = second f . second g
先程のルール4つを満たしたインスタンスは、上の式を満たします。さっそく式を書いてみましょう。インスタンスにはペアを使うことにします 。
bimap (f . g) (h . i) (a, b)
= ((f . g) a, (h . i) b)
= first f (g a, (h . i) b)
= first f (second h (g a, i b))
= bimap f h (g a, i b)
= bimap f h (first g (a, i b))
= bimap f h (first g (second i (a, b)))
= bimap f h (bimap g i (a, b))
= (bimap f h . bimap g i) (a, b)
first f
とsecond g
を合成するとbimap f g
になるので、この証明は適用されている関数をタプルの外へほどいてからbimap
にまとめることで導けます。
first (f . g) (a, b)
= ((f . g) a, b)
= first f (g a, b)
= first f (first g (a, b))
= (first f . first g) (a, b)
second (f . g) (a, b)
= (a, (f . g) b)
= second f (a, g b)
= second f (second g (a, b))
= (second f . second g) (a, b)
こちらも関数をタプルの外側に出していってから合成させて式を導出しました。
まとめ
-
Bifunctor
は値を2つ包むファンクタ - 主にタプル、Eitherがインスタンス
感想
Bifunctor
を使った例がなかなか見当たりませんでした。値を2つ包むファンクタですから、Functor
の拡張として使えばよいかと思います。Contravariant
についても調べてみます。
参考文献
-
情報が得られ次第、追記します。 ↩