HaskellのBifunctor - Functorの拡張版 #Haskell

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

再帰カインドと関係があるようですが、情報が少なくまとめられませんでした。¹

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についても調べてみます。

参考文献

情報が得られ次第、追記します。 ↩