トップ > Haskell > ファンクタであそぼう

ファンクタであそぼう

Haskell IT

この記事はHaskell Advent Calendar 2013の3日目の記事です。

目次

どうして？

ファンクタはHaskellに欠かせないものですが、ファンクタを一般化して見るという見方は意外に広まっていないように感じます。分かってしまえば単純な話だけにもったいないと思ってこの記事を書くことにしました。

また、僕は最近Thornというライブラリを作りました。これは、さまざまなデータ型から関手や畳み込み・展開をTemplate Haskellを使って自動生成するライブラリです。このライブラリを作るなかで気づいたことも合わせて書いていこうと思います。




ファンクタを拡張しよう

Haskellerなら誰しもファンクタは知っていることだと思います。言うまでもなく便利なファンクタですが、実はもっと拡張できます。

おさらい

まずはファンクタの定義を確認しましょう。

class Functor f where
  fmap :: (a->b) -> f a -> f b

(<$)というメンバもありますがここでは無視します。とにかくfmapが重要ですね。そしてファンクタ則がこれです。

fmap id == id
fmap (g.f) == fmap g . fmap f

図にするとこんな感じです。（型は大文字、関数は小文字で表すことにします。また、型が量化されているものについては適宜添え字で型を明示します。）

かなり綺麗な性質を満たしています。では、いろいろなデータをファンクタにしていきましょう。

instance Functor ((,) a) where
  fmap f (a,b) = (a, f b)
instance Functor (Either a) where
  fmap _ (Left a) = Left a
  fmap f (Right b) = Right (f b)
instance Functor ((->) a) where
  fmap f g = f . g
instance Functor Maybe where
  fmap f (Just a) = Just (f a)
  fmap _ Nothing = Nothing
instance Functor [] where
  fmap _ [] = []
  fmap f (a:as) = f a : fmap f as

これらがファンクタ則を満たすことをぜひ確認してください。
関数がファンクタになるというのが少し見慣れない感じかもしれないですが、関数がファンクタであることも重要です。また、リストでfmapが再帰的に定義されていることも重要です。
リスト以外の再帰的なデータ型も見ていきましょう。

data BinaryTree a = Tip | Bin a (BinaryTree a) (BinaryTree a)
instance Functor BinaryTree where
  fmap _ Tip = Tip
  fmap f (Bin a l r) = Bin (f a) (fmap f l) (fmap f r)

data RoseTree a = Rose a [RoseTree a]
instance Functor RoseTree where
  fmap f (Rose a rs) = Rose (f a) (fmap (fmap f) rs)

fmapがまたしても再帰的に定義されています。さらに興味深いことにRoseTreeのfmapの定義ではfmapが二重に出てきています。外側はリストに対するfmap（つまりmap）で内側がRoseTreeに対するfmapです。

引数をふたつ取ろう

さて、ペアやEitherがファンクタであることを見ましたが、どちらも部分適用された状態で定義されていて、片方の型しか使っていません。なんだか気持ち悪いですね。
そこで、ふたつの型を活かせるようなファンクタ、双ファンクタ (bifunctor) が考えられました。

class Bifunctor p where
  bimap :: (a->b) -> (c->d) -> p a c -> p b d
  first :: (a->b) -> p a c -> p b c
  second :: (b->c) -> p a b -> p a c
  bimap f g = first f . second g
  first f = bimap f id
  second = bimap id

bimapを定義すればfirstとsecondは自動的に定義されます（逆にfirstとsecondを定義すればbimapは自動的に定義されます）。
図で表すとこんな感じです。

双ファンクタ則は以下のようになっています。

bimap id id == id
bimap (g.f) (i.h) == bimap g i . bimap f h

2番目の規則を図で表すとこんな感じです。

ファンクタ則をそのまま二重にしたような感じですね。
では、いろいろなデータを双ファンクタにしていきましょう。

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

一安心ですね。

双ファンクタを応用すれば、2引数に限らず、3引数ファンクタ、4引数ファンクタ、...といくらでもつくれます。こういったファンクタの仲間をファンクタ類と呼ぶことにします。

逆転の発想

ところで、関数は双ファンクタにできないのでしょうか?
仮に関数が双ファンクタとなるのだとしたら、bimapの型は

bimap :: (a->b) -> (c->d) -> (a->c) -> (b->d)

となるはずですが、どう組み合わせても上手くいかないように見えます。*1

実際、関数を双ファンクタにすることはできません。矢印の左側（入力側）が問題になっているようです。
とりあえず、右側を固定した型を考えてみましょう。たとえば返り値をBoolに固定すれば、いわゆる述語になります。

newtype Predicate a = Predicate (a -> Bool)

さて、Predicateはファンクタでしょうか？やはり違います。Predicateは一体何なのでしょう？

そこで逆転の発想をして、反変ファンクタ (contravariant functor) というものを考えるのです。

class Contravariant f where
  contramap :: (a->b) -> f b -> f a

これが反変ファンクタです。なんだか変な感じでしょうか？
とにかく反変ファンクタ則は以下のようになっています。

contramap id == id
contramap (g.f) == contramap f . contramap g

図で表すとこんな感じです。

反変ファンクタは、ファンクタと双対の関係にあるという説明がしばしばなされます。双対というのは表・裏、左・右、上・下のようなものです。図を見ても、ファンクタと反変ファンクタでは矢印の方向がちょうど逆になっていることが分かると思います。
ちなみにファンクタは、反変ファンクタとの対比で共変ファンクタ (covariant functor) とも呼びます。

では早速Predicateを反変ファンクタにしてみましょう。

instance Contravariant Predicate where
  contramap f (Preficate p) = Predicate (p . f)
  -- f :: a -> b, p :: b -> Bool
  -- p . f :: a -> Bool

この通り、すんなりと反変ファンクタにできました。こんなこともできます。

newtype Comparison a = Comparison (a -> a -> Ordering)
instance Contravariant Comparison where
  contramap f (Comparison c) = Comparison (\x y -> c (f x) (f y))

ここまで、関数は左側（入力側）については反変ファンクタで右側（出力側）についてはファンクタであるということが分かりました。では関数はどういうファンクタにあたるのでしょうか。もう想像が付いていると思います。プロファンクタ (profunctor) というものです。

class Profunctor p where
  dimap :: (a->b) -> (c->d) -> p b c -> p a d
  lmap :: (a->b) -> p b c -> p a c
  rmap :: (b->c) -> p a b -> p a c
  dimap f g = lmap f . rmap g
  lmap f = dimap f id
  rmap = dimap id

BifunctorとContravariantを単に組み合わせただけですね。今度もlmapとrmapはdimapから導けるのでdimapだけを考えればよいです。
プロファンクタ則は次のようになっています。

dimap id id == id
dimap (g.f) (i.h) = dimap f i . dimap g h

当然ですね。では、いよいよ関数をプロファンクタにしましょう。

instance Profunctor (->) where
  dimap f g h = g . h . f

とてもシンプルですね。

以上の話をまとめると、任意の数nについて、n引数でそれぞれの引数が共変あるいは反変であるようなファンクタ類を考えることができると分かりました。かなりファンクタが拡張できましたね。バンザイ！




共変・反変・自由変・固定変

ここまでで、あるデータ型は反変ファンクタであって共変ファンクタでない、という状況があることが分かりました。
では、共変ファンクタと反変ファンクタを分けるものは何なのでしょうか。また、すべての引数を取るデータ型はなんらかのファンクタ類に属するのでしょうか。*2

データ型の整理

まず、すべてのデータ型を同型・直和型・直積型・関数型・再帰的定義という枠組みでとらえなおしていきましょう。

同型というのは、ふたつのデータ型がある意味で同じものとしてみなせるということです。
AとBが同型であるとは、

  • 関数 f :: A -> B と g :: B -> A が存在する。
  • g . f が A についての恒等関数であり、f . g が B についての恒等関数である。

という条件を満たしていることです。ここでいう関数 f と g は、実際にプログラムとして書けるのでなければなりません。*3
AとBが同型であるということを A~=B と書くことにします。
ここからは、同型なデータ型は積極的に同じものとしてみなしていきます。

直和型 A+B は、Haskellでいう Either A B にあたります。AもしくはBであるということです。直和型について交換則や結合則が成り立ちます。*4

A+B ~= B+A
(A+B)+C ~= A+(B+C)

結合則が成り立つので、結合を気にせずA+B+Cと書くことにします。

直積型 A×B は、Haskellでいう (A,B) にあたります。直積型についても交換則・結合則が成り立ちます。*5

A×B ~= B×A
(A×B)×C ~= A×(B×C)

またしても結合則が成り立つので、結合を気にせずA×B×Cと書くことにします。

直和型と直積型で分配法則も成り立ちます。

A×(B+C) ~= (A×B)+(A×C)

関数型 BA は、Haskellでいう A->B にあたります。表記が示唆するように、指数法則が成り立ちます。2番目の式はカリー化とも関連しています。

AB×AC ~= AB+C
(AB)C ~= AB×C
(A×B)C ~= AC×BC

さて、代数的データ型は大まかには次のように定義されます。

data D a b c .. =
    C1 T11 T12 T13 ..
  | C2 T21 T22 T23 ..
  ..

ここで、次のような性質が成り立っています。

D a b c .. ~= (T11×T12×T13×..) + (T21×T22×T23×..) + ..

代数的データ型は「直積の直和」にすぎないのです。
ただし、代数的データ型は再帰的な定義もできますから、右辺にDが現れることもできます。*6
型本体 (T11, T12, T13 ..) では、既存のデータ型をそのまま利用したり、組み合わせて関数型をつくったりできるわけです。

つまり、すべての代数的データ型は、同型なものを同一視すれば、基本型 (Int, Double, ..) をもとにして、直和型・直積型・関数型・再帰的定義によって作りだされたものなのです。

正の位置と負の位置

さて、最初の話に戻って、共変ファンクタと反変ファンクタを分けるものが何であるかを考えましょう。

データ型を構成する直和型・直積型・関数型のうち、直和型・直積型だけでは共変な引数しか生まれませんが、関数型がかかわると反変な引数が生まれてくる可能性があると分かりました。

ここで、継続モナドについて考えてみましょう。

newtype Cont r a = Cont ((a -> r) -> r)

aは関数の左側にあるので、Cont rは反変ファンクタでしょうか？いいえ、共変ファンクタです。

instance Functor (Cont r) where
  fmap f (Cont m) = Cont (\c -> m (c . f))

すべてのモナドは共変ファンクタであるので、当然です。
ではどうして共変ファンクタなのでしょう？関数の左側は反変だけれど、その中でさらに関数の左側になると「反変の反変」で「共変」になるようです。

「正の位置・負の位置」という考え方で、こういったことを全て説明できます。まず、基本は次の通りです。

Either (+) (+)
((+), (+))
(-) -> (+)

正の位置 (+)、負の位置 (-)というものを考えるのです。入れ子にしたらどうなるかは、もう明らかでしょう。符号の掛け算が起こるのです。

(Either (+) (+), Either (+) (+))
Either ((+),(+)) ((+),(+))
Either (-) (-) -> Either (+) (+)
Either ((-) -> (+)) ((-) -> (+))
((-), (-)) -> ((+), (+))
((-) -> (+), (-) -> (+))
(-) -> ((-) -> (+))
((+) -> (-)) -> (+)
(((-) -> (+)) -> (-)) -> (+)

正の位置・負の位置を利用すると次のことが言えるのです。

  • 引数が正の位置のみに現れる場合、その引数は共変
  • 引数が負の位置のみに現れる場合、その引数は反変

Contの定義に戻ると、aは正の位置にのみ現れているので、Cont rは共変ファンクタなのです。

データ型についてはそのデータ型を展開して考えればよくて、再帰的な定義の場合でも再帰的な定義を無限に展開したつもりで考えればいいのです。
まず、リストについて考えましょう。

data List a = Nil | Cons a (List a)

右辺を展開して符号を取ると、

Nil | Cons (+) (Nil | Cons (+) ...)

となります。どこまで行ってもaは正の位置にしか来ないので、aは共変になります。

多分木についても考えてみましょう。

data RoseTree a = Rose a (List (RoseTree a))

また符号を取ると、

Rose (+) (Nil | Cons (Rose (+) ...) (Nil | Cons (Rose (+) ...) ...))

やはりどこまで行ってもaは正の位置にしか来ないので、aは共変になります。

以上、すべての型が現れうる位置について正負の判定ができるようになりました。これで共変・反変の判定は簡単ですね。

自由変と固定変

共変・反変以外にも考えるべきものがあります。自由変 (free-variant) と固定変 (fixed-variant) です。

  • 引数が正の位置のみに現れる場合、その引数は共変
  • 引数が負の位置のみに現れる場合、その引数は反変
  • 引数が現れない場合、その引数は自由変
  • 引数が正の位置にも負の位置にも現れる場合、その引数は固定変

自由変を非変 (nonvariant)、固定変を不変 (invariant)という場合もあります。

例を挙げていきましょう。まずは自由変から。

data Const a b = Const a
data Tagged a b = Tagged b

Constにおいて、aは共変で、bは自由変です。Taggedにおいて、aは自由変で、bは共変です。
自由変は共変とも反変ともみなせる、という点で自由です。Const a は共変ファンクタにすることも反変ファンクタにすることもできます。また、Taggedは双ファンクタにすることもプロファンクタにすることもできます。

instance Functor (Const a) where
  fmap _ (Const a) = Const a
instance Contravariant (Const a) where
  contramap _ (Const a) = Const a
instance Bifunctor Tagged where
  bimap _ f (Tagged b) = Tagged (f b)
instance Profunctor Tagged where
  dimap _ f (Tagged b) = Tagged (f b)

上においてfmapとcontramap、bimapとdimapはそれぞれ定義がまったく同じになっていますね。

次は固定変の例です。

newtype ContInt r = ContInt ((Int -> r) -> r)

ContのaをIntにしただけの型です。*1 -> (+) という符号が付けられるので、rは固定変となります。
ContIntは共変ファンクタにも反変ファンクタにもなりません。
そこで次のような型クラスを考えます。

class Fixedvariant f where
  fixedmap :: (a->a) -> f a -> f a

aがまさしく「固定されている」ということが分かるでしょう。
ContIntはこのFixedvariantのインスタンスにできます。*7

instance Fixedvariant ContInt where
  fixedmap f (ContInt m) = ContInt (\c -> f (m (f . c)))

すこし変わった例だと、このようなデータ型も考えられます。

newtype What a = What (What a -> a)

右辺を展開すると

What ((What (What (... -> (+)) -> (-))) -> (+))

となり、aは正の位置にも負の位置にも現れるので、aは固定変です。
Whatの定義では、自分自身 (What a) が反変の位置に現れています。これが結構厄介なのですが、Haskellは許しています。ちなみにCoqという言語ではこのような定義を許していません。
WhatをFixedvariantのインスタンスにしてみましょう。

instance Fixedvariant What where
  fixedmap f (What g) = What (\w -> f (g (fixedmap f w)))

できましたね。

以上より、すべてのデータ型の引数は、共変・反変・自由変・固定変のいずれかになろ、すべての引数をもつデータ型は何らかのファンクタ類に属する、ということが分かりました。バンザイ！




ファンクタ類を自動生成しよう

ファンクタ類は自動生成できます。そしてその自動生成は非常にシンプルな作業によってできます。これまでファンクタ類のさまざまな綺麗な性質を見てきたので、そのシンプルさももはや不思議ではないかもしれませんね。

ファンクタ類それぞれについて型クラスを作っていたらきりがないので、fmap, contramap, bimap, dimapなどにあたる関数 (fmap類と呼ぶことにします) を自動生成することを考えます。

アルゴリズムの基本は次の通りです。

  • 代数的データ型やタプルに出会ったらとりあえずバラバラにしてそれぞれの型を加工する。
  • 関数型に出会ったら入力側と出力側を加工する。
  • 再帰的定義中で自分自身に出会ったら再帰呼び出しをする。
  • 型変数に出会ったらその変数にあった関数を適用する。
  • Intなどの基本型に出会ったら放っておく。

この際、それぞれの引数が共変/反変/自由変/固定変のいずれであるか、ということはまったく考えなくてよいのです。

たとえば次のようなデータ型を考えてみましょう。

data List a = Nil | Cons a (List a)

data Tree a b c =
    Binary (Tree a b c) a (Tree a b c)
  | Many a (List (Tree a b c))
  | Wow ((Either a b -> Maybe c) -> Tree a b c)
  | Tip

このTreeに対するfmap類をtreemapとして宣言することにします。クリスマスといえばツリーですからね。
少し頑張れば次のようにできます。

treemap :: (a->a') -> (b->b') -> (c'->c) -> Tree a b c -> Tree a' b' c'
treemap f g h (Binary l a r) = Binary (treemap f g h l) (f a) (treemap f g h r)
treemap f g h (Many a ts) = Many (f a) (listmap (treemap f g h) ts)
  where listmap _ Nil = Nil
        listmap i (Cons x xs) = Cons (i x) (listmap i xs)
treemap f g h (Wow i) = Wow (treemap f g h . i . (\x -> maybemap h . x . eithermap f g))
  where eithermap l _ (Left a) = Left (l a)
        eithermap _ r (Right b) = Right (r b)
        maybemap _ Nothing = Nothing
        maybemap j (Just c) = Just (j c)
treemap _ _ _ Tip = Tip

単純な再帰処理ですね。
あとはすこしTemplate Haskellで実装を頑張れば、データ型からfmap類を生成することができます。バンザイ！




まとめ

お疲れさまでした。長い道のりでした。
ここで扱ったことはごく基礎にすぎません。Haskellには、まだまだいくらでも奥深くて面白い世界が待っています。その世界を探求するのにこの記事が少しでも役に立てたとしたら、何よりの喜びです。
最後まで読んでくださって、本当にありがとうございました。




おまけ

Thornについて

Thornというのはルーン文字で濁らないthの発音を表すアルファベットです。Template Haskellを略すとTHになることから名づけました。
Thornには、ここで紹介したようなfmap類の生成はもちろん、一般の再帰的データ型に対して畳み込み・展開（リストでいうfoldr・unfoldr、いわゆるcatamorphismとanamorphism）を生成する機能もあります。
これからもTemplate Haskellを濫用してさまざまな面白い機能を付けていこうと思っています。
ぜひThornで遊んでみてください。

CPLであそぼう

CPL (Categorical Programming Language) という言語は僕がかなり好きなプログラミング言語です。この言語はプログラミングの概念を圏論によって記述する一環として作られたもので、非常に美しい言語です。
最初はデータ型がまったくなくて、ブール型、直和型、直積型、関数型、自然数型、リスト型を、自分で定義していきます。
さらに驚くべきことに、最初は制御構造が恒等射と射の合成しかなくて、データ型の定義と同時に制御構造が手に入るのです。ブール型とともにif文が、直和型とともにcase文が、直積型とともにペアの構成が、関数型とともにカリー化が、自然数型とともに原始再帰が、リスト型とともにfoldrが定義されます。もちろん、直和型・直積型・関数型・リスト型はきちんとファンクタ類になっています。
関数型を定義するというのがかなり変わっていますが、プリミティブには関数のかわりに射を扱います。関数はあくまで射を通して扱うデータのひとつなのです。この感覚が味わえる言語はなかなかありません。
また、無限リストなどの無限のデータ構造を扱えて、なおかつ計算停止性が保証されている、という点も興味深いです。無限リストは有限のリストとは違う扱いをされていて、無限リストと同時にfoldrではなくunfoldrが定義されます。また、計算停止性を保証するといっても表現力は豊かで、アッカーマン関数すら定義できてしまうのです。
このようにCPLはデータ型と制御構造が大変美しく結びついている言語なのです。
Haskellに対して圏論を応用しようとする前に、まずCPLで遊んでみるのもいいと思います。HackageでCPLのインタープリタが手に入ります。ぜひ遊んでみてください。

*1:型をみてその型を満たすプログラムが作れるかどうか、と考えてみることは、型の表現力が豊かであるHaskellではしばしば有用です。もうすこし高度な視点から言えば、カリーハワード対応を活用して、型を命題として見て直観主義論理上でそれを証明できるか考えてみるということです。

*2:この記事では、型引数は * の類を持つものしか考えません。たとえばモナド変換子でモナド (* -> * の類を持つ) を引数にとるような場合は考えません。

*3:ふつうの集合論で濃度が等しいということと、ここでいう同型は、区別するべきです。そもそも記述可能なプログラムは可算無限種類であるので、ある型に対する記述可能な値も高々可算無限個しかありません。Integer->Boolの型を持つ記述可能な関数の集合は、連続体濃度ではなく、可算濃度です。型をふつうの集合、関数をふつうの写像とみなす素朴な考え方は、しばしばうまくいかないので、領域理論や圏論などが使われるのです。

*4:直和の単位元は、Haskellでは特にプリミティブには用意されていません。直和型の単位元はしばしばボトム型と呼ばれます。ボトム型の値はない（あるいは計算が停止しない状態しかない）ということが重要です。Haskellでいえば、Void型が実質的にボトム型であるとみなせます。

*5:直積型の単位元はHaskellではユニット型にあたります。ユニット型の値は一つしかないということが重要です。

*6:右辺で現れるDは左辺と同じく D a b c .. となっているのが標準的です。そのようなデータ型を正則なデータ型といいます。それに対し、そうでないデータ型、例えば右辺で D (a,a) b c .. などとなっているようなものは、非正則なデータ型といいます。この記事では基本的に正則なデータ型のみを扱います。

*7:Fixedvariantについてファンクタ則のような「外側から見た規則」を作り出すことは難しいです。Fixedvariantのインスタンスは、ファンクタや反変ファンクタのインスタンスと同様な「自然な形」で定義する、ということにします。ファンクタ類の生成方法については後述します。

*1:+) -> (-