Help us understand the problem. What is going on with this article?

HaskellのBifunctor - Functorの拡張版

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のインスタンスにしたければ、bimapfirstsecondを実装せよ、とあります。firstsecondbimapはお互いを呼び出しあっています。

bimapfmapと同じく包まれた値に関数を適用するのですが、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)

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

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

参考文献


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

Izawa_
Haskell使いです。記事はあまりモナモナしてません。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした