Chapter 27

7.1 プログラムにおける関手

さのたけと
さのたけと
2021.05.31に更新

現実的なプログラミングの話に移ろう.我々は型の圏と関手という道具を持っている.ここで,型の圏をそれ自身にマッピングする関手(自己関手 (endofunctor))について考えてみよう.型の圏の自己関手とはどんなものだろうか? まず第1に,型を型にマッピングするだろう.意識していないかもしれないが,このようなマッピングを我々はすでに知っているはずだ.型をパラメータにもつ型として定義されるものがそれである.いくつか例を見ていこう.

Maybe Functor

Maybe は,型 a を型 Maybe型にマッピングする.

data Maybe a = Nothing | Just a

Maybe それ自体は型ではなく,型コンストラクタ だというのが巧妙な部分だ.IntBool といった型を引数として与える必要がある.引数なしの Maybe は型の関数という意味になる.しかし,この Maybe は関手なのだろうか? (以降では関手という単語をプログラミングの文脈での関手(そしてほとんどの場合は自己関手)として使うことにする.)関手は対象(ここでは型)だけでなく射(ここでは関数)もマッピングするので,型 a から型 b への関数 f から,Maybe a から Maybe b への関数をつくりたい.

f :: a -> b

このような関数を定義するには,2つの Maybe コンストラクタに対応する2つのケースを考える.引数が Nothing の場合は簡単で,単に Nothing を返すだけでよい.引数が Just の場合は,Just の中身に関数 f を適用する.したがって Maybe ファンクタによる関数 f の像は次のようになる.

f' :: Maybe a -> Maybe b
f' Nothing = Nothing
f' (Just x) = Just (f x)

(Haskell では変数名にアポストロフィを使うことができて,こういう時に便利だ.)Haskell では,関手の性質の一つである射のマッピングを,高階関数 fmap で実装できる.Maybe の場合,次のようなシグネチャになる.

fmap :: (a -> b) -> (Maybe a -> Maybe b)

しばしば,fmap は関数を「持ち上げる」と表現される.持ち上げられた関数は Maybe された値の間の関数になる. fmap のシグネチャはカリー化の考え方を用いて2通りに解釈できる.引数が (a -> b) で返り値が (Maybe a -> Maybe b) の関数という解釈か,あるいは引数を2つ取って Maybe b を返す関数という解釈である.

fmap :: (a -> b) -> Maybe a -> Maybe b

これまでの考え方をつかうと,Maybefmap する実装は次のようになる.

fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)

型コンストラクタ Maybe と関数 fmap で関手になることを示すためには, fmap が恒等射を保存し,合成可能であることを確認すればよい.これらは関手性 (functor laws) などと呼ばれるが,圏の構造が保たれるかを確認しているだけだ.

等式推論 (Equational Reasoning)

関手性を確認するのに,Haskell でよく登場する証明テクニックである 等式推論 (equational reasoning) を使ってみることにする.これは Haskell の関数が等式の形で定義されていることを利用している.変数名が衝突しないように名前を変える必要があるかもしれないが,左辺の形と右辺の形に書き換えることができるということだ.これは関数のインライン化や,式 (expression) から関数へのリファクタリングに対応する.恒等関数を例にしてみよう.

id x = x

式の中に id y という部分を見つけたら,それは y と置き換え(インライン化)できるということだ.あるいは, id (y + 2) のように id が式に適用されているのを見つけたら,その部分は式自体である (y + 2) に置き換えできるということだ.この置き換えは双方向に行えるので,任意の式 eid e に置き換える(リファクタリングする)こともできる.関数がパターンマッチングの形で定義されている場合は,各々のパターンを独立に使える.例えば,上で定義した fmap の場合,fmap f NothingNothing に置き換えられるし,その逆も可能である.これが実用上どのように働くか見てみよう.恒等関数の保存からスタートする.

fmap id = id

ここでは NothingJust の2つのケースを考える.Nothing のケースについては,

fmap id Nothing
= {fmap の定義より}
  Nothing
= {id の定義より}
  id Nothing

となる.(ここでは左辺から右辺への変形を, Haskell の疑似コードで表現した.)最後のステップでは, id の定義を逆向きに使っている.式 Nothing を式 id Nothing に置き換えているのだ.実際には,このような証明を左辺と右辺の両側から,同じ式(ここでは Nothing)にたどり着くまで進めることになる[1]Just のケースも簡単だ.

fmap id (Just x)
= {fmap の定義より}
  Just (id x)
= {id の定義より}
  Just x
= {id の定義より}
  id (Just x)

fmap が射の合成を保存するかについてもみておこう.

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

まず Nothing のケースはこうだ.

fmap (g . f) Nothing
= {fmap の定義より}
  Nothing
= {fmap の定義より}
  fmap g Nothing
= {fmap の定義より}
  fmap g (fmap f Nothing)

Just のケースはこうなる.

fmap (g . f) (Just x)
= {fmap の定義より}
  Just ((g . f) x)
= {関数の合成の定義から}
  Just (g (f x))
= {fmap の定義より}
  fmap g (Just (f x))
= {fmap の定義より}
  fmap g (fmap f (Just x))
= {関数の合成の定義から}
  (fmap g) . (fmap f) (Just x)

ここで,等式推論は C++ のように副作用を持つ「関数」では使えないことを強調しておこう.例えばこのようなコードだ.

int square(int x) {
    return x * x; 
}

int counter() {
    static int c = 0;
    return c++;
}

double y = square(counter());

等式推論を無理やり使ってみると,

double y = counter() * counter();

となるが,この変換は明らかに正しくないし,実行結果も異なる.にもかかわらず C++ コンパイラは,square をマクロで定義した場合にはこのような等式推論を試みて,悲惨な結果になる.

Optional

Haskell では関手を表現するのは容易だが,ジェネリックプログラミングが可能で高階関数をサポートしていればどんな言語でも定義できる.ためしに,Haskell の Maybe のようなものを C++ の型テンプレート optional で作ってみよう.実装の概略を以下に示す.(実際には,渡される引数に対する様々な処理,コピーセマンティクス,C++ 特有のリソース管理などのために,より複雑になる.)

template<class T>
class optional { 
    bool _isValid; // the tag
    T _v;
public:
    optional()    : _isValid(false) {}        // Nothing
    optional(T x) : _isValid(true) , _v(x) {} // Just
    bool isValid() const { return _isValid; }
    T val() const { return _v; } };

これで,関手の性質の一つである「型のマッピング」ができるようになった.任意の型 T が,新しい型 optional<T> にマッピングされるわけだ.次に関数を与えたときのふるまいを定義しよう.

template<class A, class B>
std::function<optional<B>(optional<A>)>
fmap(std::function<B(A)> f) { 
    return [f](optional<A> opt) { 
        if (!opt.isValid()) 
            return optional<B>{};
        else 
            return optional<B>{ f(opt.val()) };
    };
}

これは高階関数で,引数として関数を受け取って関数を返す.カリー化を使わないのならば,次のように書ける.

template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) { 
    if (!opt.isValid())
        return optional<B>{};
    else 
        return optional<B>{ f(opt.val()) };
}

fmap を,optional のテンプレートメソッドとして書くこともできる.このように C++ での関手のパターンには選択肢が多すぎて問題になる.関手をインターフェースとして継承すべきか?(不幸なことにテンプレート仮想関数は無い.)カリー化するのとしないのとではどちらがよいのだろう? C++ コンパイラは型を正しく推論できるだろうか? あるいは型推論を期待せずに指定すべきだろうか? int をとり bool を返す関数 f が入力されるという状況を考えてみよう.コンパイラはどのようにして g の型を見つけるのだろうか.

auto g = fmap(f);

特に,今後 fmap をオーバーロードする関手が増えていったらどうなるだろう?(しかも,すぐにそうなるのだ.)

型クラス (Typeclasses)

Haskell では,どうやって関手をとりあつかっているのだろうか? 型クラスがその答えである.型クラスは,共通のインターフェースを持つ型をひとまとめにして定義する.例えば,等号を持つ対象のクラスは次のように定義される.

class Eq a where
    (==) :: a -> a -> Bool

この定義は,「型 a の引数を二つとって Bool を返す (==) という演算子がサポートされているならば,型 aEq クラスである」と言っている.Haskell 対して,特定の型が Eq であると伝えるには,その型がクラス Eqインスタンスだという宣言と, (==) の実装が必要ということだ.例えば,2D の点を表現する Point (二つの Float の直積型)があったとすると,

data Point = Pt Float Float

点と点が等しいことは次のように定義できる.

instance Eq Point where
  (Pt x y) == (Pt x' y') = x == x' && y == y'

ここでは, (==) を中置演算子として(Pt x y)(Pt x' y') の間に置いた.関数の本体は等号の後ろである.ひとたび PointEq クラスのインスタンスとして宣言してしまえば,点が等しいかどうかを直接的に比較することができるようになる.ここで気を付けたいのは,C++ や Java と違って, Point 型の定義においてそれが Eq クラス(あるいはインターフェース)であることを記述する必要は無い.クライアントコードのなかで後から宣言してもかまわないのだ.型クラスは関数(と演算子)をオーバーロードするための, Haskell 固有の仕組みである.我々は異なる関手に対して fmap をオーバーロードしたいのだが,ここでややこしいのは,関手を型ではなく,型のマッピングとして定義したいということだ.Eq のときもそうだったが,我々がほしいのは型の集まりではなく,型コンストラクタなのだ.ありがたいことに, Haskell の型クラスは型と一緒に使えるだけでなく,型コンストラクタと一緒に使うこともできる.

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

このコードは,「ここで指定したシグネチャの fmap 関数が存在するような fFunctor である」と言っている.小文字の f は型変数で, ab と似たようなものだ.しかしながら,コンパイラは ff af b のように他の型に作用する形でつかわれていることから, f は型ではなく型コンストラクタであると推論する.したがって, Functor のインスタンスを宣言するときには,型コンストラクタに fmap を与えなければならない. Maybe の場合にはこうなる.

instance functor Maybe where
    fmap _ nothing = nothing
    fmap f (Just x) = Just (f x)

Functor クラスと,Maybe をはじめとしたそのたくさんのインスタンス達は,標準の Prelude ライブラリに含まれている.

C++ のファンクタ

同じようなアプローチを C++ にも使えるだろうか? 型コンストラクタに相当するのは optional のようなテンプレートクラスになる. テンプレートパラメータを使って F にパラメータを持たせるのだ.こういう書き方になる.

template<template<class> F>, class A, class B>
F<B> fmap(std::function<B(A)>, F<A>);

このテンプレートを別の関手に特化させてみよう.残念なことに C++ のテンプレート関数を部分的に特殊化することはできない.つまり次のように書くことはできない.

template<class A, class B>
optional<B> fmap<optional>(std::function<B(A> f, optional<A> opt)

しかたがないので,代わりに関数のオーバーロードを使う.カリー化されていない方の fmap の定義を使う形になる.[2]

template<class A, class B>
optional<B> fmap(std::function<B(A)> f, optional<A> opt) {
    if (!opt.isValid())
        return optional<B>{};
    else
        return optional<B>{ f(opt.val()) };
}

この定義は動きはするのだが,fmap の2番目の引数がオーバーロードを処理しているというだけだ. fmap のもっと汎用的な定義については完全に無視されてしまう.[3]

List 関手

プログラミングにおける関手の役割について感覚的に理解するために,もう少し例を見てみよう.型をパラメータに持つ型はすべて,関手になりうる.たとえば一般的なコンテナは,保持する要素の型をパラメータに持つので関手になりうる.まずはとても単純なコンテナであるリストについて見てみよう.

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

型コンストラクタ List は,任意の型 aList 型にマッピングする. List が関手であることを示すには,ある与えられた関数 a -> b から List a - List b への持ち上げを定義しなければならない.

fmap :: (a -> b) -> (List a -> List b)

List a を引数にとる関数は,2つのリストコンストラクタに対応していなければならない. Nil の場合は単純で, Nil を返せばよい.空のリストに対してできることはほとんどない. Cons の場合は再帰を使うことになるので,少しトリッキーになる.少し立ち戻って,我々が何をしたかったのか思い出そう.やりたかったのは, List a と, a をとって b を返す関数 f から, b のリストを生成することだ.では,(空でない)リストが head[4] と tail[5]Cons したものとして定義されているとき,これをどうしたらよいのだろうか? head には関数 f を作用させ, tail には関数 f を持ち上げた (fmap した)ものを作用させればよい.これは再帰的な定義なのは,持ち上げられた f は次のように定義できる.

fmap f (Cons x t) = Cons (f x) (fmap f t)

右辺において fmap f が元のリストより短いリストである tail に作用している点に注目してほしい.再帰的にリストをどんどん短くしていくことになるので,繰り返していけば最終的には空リスト Nil になる.前述のとおり, Nilfmap f を作用させた場合に Nil を返すと決めてある.よって,新しい head である (f x) と,新しい tail である (fmap f t)Cons コンストラクタで結合させたものが最終的な結果になる.以上をまとめると,リスト関手の定義は次のようになる.

instance Funcor List where
  fmap _ Nil = Nil
  fmpa f (Cons x t) = Cons (f x) (fmap f t)

もし C++ のほうが馴染みがあるなら,最も知られた C++ コンテナである std::vector について考えてみよう. std::vector に対する fmap は, std::transform の軽い[6]カプセル化で実装できる.

template<class A, class B>
std::vector<B> fmap(std::function<B(A)> f, std::vector<A> v) {
  std::vector<B> w;
  std::transform( std::begin(v)
                , std::end(v)
                , std::back_inserter(w)
                , f);
  return w;
}

たとえば,数の列について,各要素を二乗する場合はこうなる.

std::vector<int> v{ 1, 2, 3, 4 };
auto w = fmap([](int i) { return i*i; }, v);
std::copy( std::begin(w)
         , std::end(w)
         , std::ostream_iterator(std::cout, ", "));

std::transformfmap のよりプリミティブな親戚といえる. std::transform 用のイテレータを実装すれば,C++ コンテナの多くは関手になる.イテレータや一次変数の記述が煩雑なので,残念ながら関手のシンプルさは失われている.(前述の fmap の実装と見比べてほしい.)新しく提案されている C++ の ranges ライブラリでは,ranges の関手的な性質をより明らかなものにしているのは嬉しいことだ.

Reader 関手

ここまで読み進んできた読者は,関手はコンテナの一種だといったような印象を持ったかもしれない.これから,一見するとまったく異なる例を見てみよう.型 a から,返り値が型 a の関数へのマッピングを考えてみる.我々はこれまで,関数の型についてそれほど掘り下げてきておらず,圏論的にちゃんと扱い始めるのはこれからだ.だが,プログラマである我々は既にいくらかのことを知っている. Haskell では,関数の型を組み立てるのにアロー型コンストラクタ (->) を使う.アロー型コンストラクタには,引数タイプと返り値タイプの2つがある.今まで見てきたのは a -> b という中置記法の形だが,-> を括弧でくくって前置記法で書いても全く等価だ.

(->) a b

2つ以上の引数をとる関数は部分適用ができたように,アロー型コンストラクタに引数の型を1つだけ部分適用できて,その場合 (->) は2つ目の引数が来ることを期待するので,

(->) a

は型コンストラクタである.これにもう一つの型 b を与えれば, a -> b という完全な形の型になる.これは a でパラメータ化された型コンストラクタ群を定義したことになる.これが関手であるかどうか見ていこう.型パラメータが2つあると混乱しやすいので,以前使った関手の定義にあわせて引数の型を r ,返り値の型を a としよう.すると,この型コンストラクタは任意の型 ar -> a へマッピングするということになる.これが関手であることを示すためには,関数 a -> b を持ち上げた, r -> a から r -> b への関数が欲しい. r -> ar -> b も型コンストラクタ (->) r によって生成される型である.そこで, (->) rfmap の型シグネチャに当てはめてみると,次のようになる.

fmap :: (a -> b) -> (r -> a) -> (r -> b)

関数 f :: a -> b と関数 g :: r -> a が与えられたとき,関数 r -> b を作れるだろうか.2つの関数を合成する方法は一つしかないが,それは我々がまさに欲しいものになっている.つまり fmap の実装は次のように書ける.

instance Functor ((->) r) where
  fmap f g = f . g

うまくいった! もしもっと簡潔な表現が好みなら,前置記法に書き直して,

fmap f g = (.) f g

さらに引数を省略することで,二つの関数を等号で結んだ形にまで単純化できる.

fmap = (.)

この fmap の実装と型コンストラクタ (->) r の組み合わせは, reader 関手と呼ばれている.

(和訳:@takase

脚注
  1. 原文では burning the candle at both ends ↩︎

  2. Instead, we have to fall back on function overloading, which brings us back to the original definition of the uncurried fmap ↩︎

  3. This definition works, but only because the second argument of fmap selects the overload. It totally ignores the more generic definition of fmap. ↩︎

  4. 先頭の要素 ↩︎

  5. 先頭以外の要素のリスト ↩︎

  6. thin ↩︎