Haskell の Eq と Ord クラスを C++ で作る

プログラムをたくさん書く生活になりつつある．C++, Java, Python, 必要ならその他も．．．加えてプライベートな勉強会に参加して，Haskellを学んでいる．1年前は高階関数なんじゃらほいって感じだったが，今ではそれが気軽に使えない言語だと，その代替としてループを回すコードを書くのがひどく苦痛に感じている．．．

C++ でも高階関数使いたいなぁーと思うようになってきているが，そもそも C++ の多相性と Haskell の多相性は同等の表現力があるのか？という疑問が湧き，C++ で Haskell に相当する Eq クラスと Ord クラスは書けるのか！？と思ったので書いてみることにした．

Haskell には型クラスがあり，これは Java でいうところの interface である．すなわち，その型が持つ機能の一面を表現するために使われる．基本型クラスの一つである Eq とは，(==) と (/=) (C++ では operator== と operator!= に相当) が定義されている型クラスで，同等および非同等を表現できる型が継承すべきインターフェースである．
また，Ord はこれに加えて，(<)と(>)，(<=)，(>=) が定義される．すなわち，全順序関係である．全順序ではない中途半端な順序関係も表現できたかも知れないが，普段はまず使わないので，今は考えないことにする．

目的は，同じことを二回以上書かずにコードを書くことである．言語における多相性(ポリモーフィズム)のサポートがそれを可能にする．多相性の表現方法は Haskell と C++ でそれぞれ違う．パラメータ多相，アドホック多相，部分型多相の 3 種類あるそうだ．
参考: http://d.hatena.ne.jp/kazu-yamamoto/20081024/1224819961
C++にはテンプレートと多重継承があり，また純粋仮想関数が定義できる．これらの使い方が最初はもやもやとしてよく分からなかったが，ググりつつ，本を眺めつつ，コードと格闘しているうちになんとなく分かってきた．

まずは，コードを見てみよう．

/**
 * Type class definition like Haskell in C++.
 */

#ifndef TYPECLASS_HPP_
#define TYPECLASS_HPP_

namespace TypeClass {

    template <class T>
    class Eq
    {
    public:
        virtual bool operator==(const T& right) const = 0;
        bool operator!=(const T& right) const {
            return ! (*this == right);
        };
    };

    template <class T>
    class Ord : virtual public Eq<T>
    {
    public:
        virtual bool operator<(const T& right) const = 0;
        bool operator<=(const T& right) const {
            return (*this < right || *this == right);
        };
        bool operator>(const T& right) const {
                return ! (*this <= right);
        };
        bool operator>=(const T& right) const {
            return ! (*this < right);
        };
    };
}

#endif /* TYPECLASS_HPP_ */

まず，Eq もしくは Ord を継承する任意の型Tで，わざわざ引数の型を変えたコードを書かなくて済むように，パラメトリック多相性を実現するテンプレートを使う．

次に，

virtual bool operator==(const T& right) const = 0;

のように型Tによって，実際の振舞が変わり得るメンバ関数は，純粋仮想関数として型定義(プロトタイプ宣言)のみを行う．実際の定義は，型クラスを継承する型の定義時に行う．純粋仮想関数を用いることで Eq や Ord は実体を作ることが出来なくなり，それを継承した型のみで使われることを保証でき，また，同じ名前の関数(==)でも型によって振舞を変えるアドホック多相を実現できる．

次に，Eq に関しては (==) が決まれば，自動的に (/=) が決まり，Ord に関しては，(==) と (<) さえ決まれば残りが自動的に決まる．

bool operator!=(const T& right) const {
    return ! (*this == right);
};

このように，非同等は同等の否定であるため，Eq を継承するほとんどの型は，このデフォルト実装をそのまま使うことが出来，新たに定義する必要がない．だから，(==) と (<) 以外はこれらの型クラスを継承する型において，わざわざ定義したくない．そこで，デフォルト実装を使う．デフォルト実装は，通常のメンバ関数として定義する．(仮想型でない型同士の継承関係が子孫にあり，その振舞を動的に決定したい場合は，virtual をつけておく必要がある．部分型多相が実現される．)

Ord クラスは Eq クラスの性質を包含するため，型クラス同士の継承関係を記述する．

class Ord : virtual public Eq<T>

すなわち，Ord を継承する型は，自動的に Eq も継承することになり，(==) を定義する必要がある．
C++は多重継承を許すシステムのため，通常の継承を行うと，同一クラスが祖先に複数回登場することがあり，それらは別々の実体を持つため，対象を一意に決められず，コンパイルに失敗する．virtual をつけて仮想継承することで，同じ型が祖先にいる場合はその実体を共有させることでこの問題を回避する．今回は Eq および Ord は多重継承していないため，仮想継承しなくても挙動は変わらないが，子孫となる型クラスをさらに定義するときに多重継承を用いる場合を想定して，virtual をつけておく．

実際に Eq と Ord を使ったプログラム例を示す．

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#include "typeclass.hpp"

class A : virtual public TypeClass::Eq<A>
{
public:
    int i;
    bool operator==(const A& right) const {
        return i == right.i;
    };
};

class B : virtual public TypeClass::Ord<B>
{
public:
    int i;
    bool operator==(const B& right) const {
        return i == right.i;
    };
    bool operator<(const B& right) const {
        return i < right.i;
    };
};

int rand(int max)
{
    return (int)(rand() / ((double) RAND_MAX + 1.0f) * (double)max);
}

int main()
{

    srand(time(0));
    
    A a1, a2;
    a1.i = rand(100);
    if (rand(2))
        a2.i = a1.i;
    else
        a2.i = rand(100);

    assert((a1 == a2) == (a1.i == a2.i));
    assert((a1 != a2) == (a1.i != a2.i));

    B b1, b2;
    b1.i = rand(100);
    b2.i = rand(100);

    assert((b1 < b2) == (b1.i < b2.i));
    assert((b1 <= b2) == (b1.i <= b2.i));
    assert((b1 > b2) == (b1.i > b2.i));
    assert((b1 >= b2) == (b1.i >= b2.i));

    return 0;
}

型A は Eq のインターフェースを持ち，型B は Ord のインターフェースを持つ．Eq，Ord はテンプレートで実現されているため，それぞれの型名を与えて必要な関数プロトタイプ宣言を自動生成させる必要がある．A と B は，どちらも int 型の変数を持ち，それを直接比較した場合と，型Aおよび型Bとして比較したときに同じ結果になることを確認するだけの簡単なものである．これで，Eq と Ord を使って同じような記述を複数回することなく最小限の定義だけで型クラスを使ったプログラムが書けた．

気が向いたら，もう少し複雑なこともするかも知れない．