inkar-us-i.hatenablog.com


先日OCamlのFunctorという新たな多相性の実現方法を学んだので、せっかくなので各言語のアドホック多相性についてまとめてみたいと思います。

クラスとその継承ではなく、アドホックな方法で多相を実現する手段はいくつかありますが、その根本にあるアイデアはすべて同じです。

以下では、例としてどの言語でも、「同値比較のできる型tについて、tのリストから特定の値を探す」関数を定義します。

クラスの継承による多相

アドホックな多相の話をする前に、まずは大部分の言語に存在する継承による多相を見てみましょう。

import java.util.*;

interface Eq<T> {
    public boolean equalTo(T that);
}

class Person implements Eq<Person> {
    // 例を簡単にするために、パブリックなプロパティを用意しています
    public String name;
    public int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public boolean equalTo(Person that) {
        if (that instanceof Person) {
            Person t = (Person)that;
            return this.name.equals(t.name) &&
                this.age == t.age;
        } else {
            return false;
        }
    }
}

class Find {
    public static <T extends Eq<T>> T find(T e, List<T> xs) {
        for (T x : xs) {
            if (e.equalTo(x)) {
                return x;
            }
        }
        return null;
    }
}

あまりJavaらしくないかもしれませんが、これは後にでてくる関数型言語との比較のためです。
こういった多相性の実現方法の欠点は、Person型を作る時点でわかっているインターフェースしか実装することができないことです。
Person型を作った時点ではまだEqインターフェースは存在していなく、後になってPersonの同値比較をしたくなった場合、この方法ではあらたにPersonにEqの実装を追加する方法がありません。

アドホック多相の基本的なアイデア

ではアドホック多相ではどのように多相を実現しているかというと、多相性が必要な部分(先ほどで言えば同値比較関数)を何らかの方法で別に渡してしまおうという考え方に基づいています。

data Person = Person {
    name :: String
  , age :: Int
  }

personEq :: Person -> Person -> Bool
personEq a b = name a == name b && age a == age b

find :: (a -> a -> Bool) -> a -> [a] -> Maybe a
find _ _ [] = Nothing
find eq e (x : xs)
  | eq e x = Just x
  | otherwise = find eq e xs

このfind関数は比較方法を受け取って、その比較方法に基づいてリストの中から要素を検索しています。
また、このような関数が複数存在する場合は、1つのデータ構造にまとめることも多いです。

data Eq a = Eq a {
  eq :: a -> a -> Bool
  }

しかし、これらの関数やデータ構造を直接渡すのは面倒です。
アドホック多相性を扱う方法はいくつかありますが、その方法はいずれも「このデータ構造をどれだけ簡単に渡すか」という考え方に基づいています。

型クラスを使った多相性

型クラスに関する構文を言語に組み込むと、こういった多相性を簡単に実現することができます。

class Eq a where
  eq :: a -> a -> Bool

instance Eq Person where
  eq a b = name a == name b && age a == age b

find :: Eq a => a -> [a] -> Maybe a
find _ _ [] = Nothing
find eq e (x : xs)
  | eq e x = Just x
  | otherwise = find eq e xs

このとき、型クラスEqのメソッドeqは、aの型によって一意的に決まります。
したがって、わざわざeqを引数などで持ちまわる必要がなくなり、コードが簡潔に書けるようになります。
この方法は以下で紹介する他の方法よりも簡潔に書くことができますが、型クラスCの型Tによる実装を、コード中に1種類しか持つことができないという弱点もあります。

暗黙引数を使った多相性

Scalaの型クラスはtraitを用いて実現されているとよく言われますが、本当に重要なのは暗黙引数の方です。

trait Eq[T] {
  def eq(a: T,b: T): Boolean
}

case class Person(name : String, age : Int)

object PersonEq extends Eq[Person] {
  def eq(a: Person, b: Person): Boolean =
    a.name == b.name && a.age == b.age
}

object Find {
  def find[T](e: T, xs: List[T])(implicit E : Eq[T]): Option[T] =
    xs match {
      case Nil => None
      case x :: xs_ =>
        if (E.eq(e, x))
          Some(x)
        else find(e, xs_)
    }
}

使う側では

implicit val PEq: Eq[Person] = PersonEq

などとしてから、Find.findを呼びます。
この暗黙引数は、別にtraitでなくても構わないわけです。例えば、次のようにfindを実装することもできます。

  def find2[T](e: T, xs: List[T])(implicit eq: (T, T) => Boolean): Option[T] =
    xs match {
      case Nil => None
      case x :: xs_ =>
        if (eq(e, x))
          Some(x)
        else find2(e, xs_)
    }

何にせよ、この暗黙引数という機能があるおかげで、使う側では一々

Find.find(e, xs)(PersonEq)

などというように書かなくても良くなるわけです。
この方法は状況に合わせてEq[Person]を様々にカスタマイズできるという点でHaskellの型クラスより柔軟性が高いですが、暗黙引数というかなり大きなものを言語仕様に組み込んでしまったため、変な書き方をすれば一気にコードがわけのわからないものになってしまうというデメリットもあります。

Functorを使う

OCamlアドホック多相性の実現方法は大胆で、なんと「モジュール単位で引数を受け取ってしまおう」という考え方に基づいています。

(*
 * モジュールの「型」を定義
 * モジュールであることを除けば、Scalaのtraitの定義に近い
 *)
module type Eq =
  sig
    type a
    val eq : a -> a -> bool
  end

type person =
  | Person of string * int

module PersonEq : (Eq with type a = person) =
  struct
    type a = person
    let eq a b = match (a, b) with
      | (Person(a_name, a_age), Person(b_name, b_age)) ->
         a_name = b_name && a_age = b_age
  end

module type Find =
  sig
    type a
    val find : a -> a list -> a option
  end

module Find (E : Eq) : (Find with type a = E.a) =
  struct
    type a = E.a
    let rec find (e : a) (xs : a list) : a option =
      match xs with
      | [] -> None
      | x :: xs' ->
         if E.eq e x
         then Some(x)
         else find e xs'
  end

最後に定義したモジュールFindは、module type Eqに属するモジュールを受け取り、findが定義されたモジュールを返すという「関数」のようなものになっています。
モジュール単位でEqを受け取れば、その中にある関数では一々Eqを引数に取らなくても大丈夫、という考え方です。
Haskellと違って一つの型のEqの実装を複数用意できますし、一旦モジュールの引数に型クラスの実装を渡してしまえば、内部の関数に渡す必要はなくなります。