HaskellのBifunctor - Functorの拡張版


`Bifunctor`ってなんだよ、っていうと型引数を2つとる`Functor`の兄弟です。語源は*bi-functor*という造語だと思われます。*bi-*は2つの、とか共通の、という意味があるので「双関手」と訳します。

## 定義

```haskell
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`をインポートします。

```haskell
Prelude> :m Data.Bifunctor
Prelude Data.Bifunctor>
```

`Bifunctor`のインスタンスはいくつかありますが、なじみ深いのは`Either`かと思われます。

```haskell
instance Bifunctor Either where
    bimap f _ (Left a) = Left (f a)
    bimap _ g (Right b) = Right (g b)
```

`Left`でも値がスルーされずに、ちゃんと関数が適用されてくれます。

```haskell
Prelude Data.Bifunctor> bimap (+5) length $ Right [1,2,3]
Right 3
Prelude Data.Bifunctor> bimap (+5) length $ Left 10
Left 15
```

## Bifunctorのルール

型をインスタンスにする際に守らなければならないルールがいくつかあります。

```haskell
1. bimap id id = id
2. first id = id
3. second id = id
4. bimap f g = first f . second g
```

上の3つは値が保存されること、4つ目は関数合成についてのルールです。

## インスタンスたち

### タプル

```haskell
instance Bifunctor (,) where
    bimap f g ~(a, b) = (f a, g b)
```

標準ライブラリでは5タプルまでがインスタンスとして実装されています。全て最後の2つの要素に関数が適用されます。

```haskell
Prelude Data.Bifunctor> bimap (+2) (+10) (1,2)
(3,12)
Prelude Data.Bifunctor> bimap (++" world") (^2) ("hello", 10)
("hello world",100)
```

ルールを満たしていることを証明します。

```haskell
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

```haskell
instance Bifunctor Either where
    bimap f _ (Left a) = Left (f a)
    bimap _ g (Right b) = Right (g b)
```

挙動は先程説明したとおり、`Left`か`Right`かに関わらず関数は適用されます。ルールを証明してみます。

```haskell
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の法則

```haskell
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つを満たしたインスタンスは、上の式を満たします。さっそく式を書いてみましょう。インスタンスにはペアを使うことにします 。

```haskell
  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`にまとめることで導けます。

```haskell
  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)
```

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

## 参考文献

- [Hackage - Data.Bifunctor](http://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Bifunctor.html)
- [指圧記 - ファンクタで遊ぼう](http://shiatsumat.hatenablog.com/entry/20131203/p1)

[^1]: 情報が得られ次第、追記します。