Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?

More than 1 year has passed since last update.

@Izawa_

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. 情報が得られ次第、追記します。 

0
Help us understand the problem. What is going on with this article?
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
0
Help us understand the problem. What is going on with this article?