関数型の考え方: Either ツリーとパターン・マッチング

Either と Generics を使用して、Java で Scala スタイルのパターン・マッチングを作成する

Scala では、パターン・マッチングに基づいてディスパッチを実行することができます。これは、Java 開発者にとってはかなり羨ましい機能です。今回の記事では、Pure Java において標準的なデータ構造と Generics を組み合わせて、パターン・マッチングのような構文を使用する方法を説明します。

Neal Ford, Software Architect / Meme Wrangler, ThoughtWorks Inc.

Neal FordNeal Ford は世界的な IT コンサルティング企業である ThoughtWorks のソフトウェア・アーキテクトであり、Meme Wrangler でもあります。また彼は、アプリケーション、教育資料、雑誌記事、コースウェア、ビデオや DVD によるプレゼンテーションなどの設計と開発も行っています。さまざまな技術に関する本の著者、編集者でもあり、最新の著書は『プロダクティブ・プログラマ ― プログラマのための生産性向上術』です。彼は大規模なエンタープライズ・アプリケーションの設計や構築を専門にしています。また彼は世界各地で開催される開発者会議での講演者としても国際的に有名です。彼の Web サイトをご覧ください。



2012年 8月 09日

この連載について

この連載の目的は、読者の皆さんの考え方を関数型の発想へと方向転換し、よくある問題を新たな考え方で検討することによって、日常的なコーディングの改善方法を見つけるお手伝いをすることです。そのために、関数型プログラミングに特徴的な概念、関数型プログラミングを Java 言語で行えるようにするフレームワーク、JVM 上で動作する関数型プログラミング言語、そして今後、言語設計を学習する上での方向性などについて詳しく探ります。この連載の対象読者は、Java および Java の抽象化がどのように機能するかは知っていても、関数型言語を使用した経験がほとんど、あるいはまったくない開発者です。

前回の記事では、関数型プログラミングの世界で共通して使用されている抽象クラス、Either を紹介しました。今回も引き続き Either について探り、Either を使ってツリー形式の構造を作成します。その目的は、Scala のパターン・マッチングを模倣して、トラバース・メソッドを作成できるようにすることです。

Either が Java の Generics を使用すると、2 つの型のうちのいずれかを受け入れる単一のデータ構造になります。2 つの型は、leftright の部分にそれぞれ格納されます。

前回の記事で取り上げたローマ数字パーサーの例では、EitherException (left) または Integer (right) のいずれかを格納します (図 1 を参照)。

図 1. 2 つの型のいずれか一方を格納する Either の抽象化
2 つの型のいずれか一方を格納する Either の抽象化

前回の例では、以下の代入によって Either にデータを取り込みました。

Either<Exception, Integer> result = RomanNumeralParser.parseNumber("XLII");

Scala のパターン・マッチング

Scala が持つ便利な機能の 1 つは、パターン・マッチングを使用してディスパッチできる機能です (「参考文献」を参照)。この機能は説明するよりも例を示すほうが簡単なので、リスト 1 に示す関数について検討してみましょう。この関数は、数値のスコアを文字による等級に変換する関数です。

リスト 1. Scala のパターン・マッチングを使用して、スコアに応じた文字の等級を割り当てる
val VALID_GRADES = Set("A", "B", "C", "D", "F")


def letterGrade(value: Any) : String = value match {
  case x:Int if (90 to 100).contains(x) => "A"
  case x:Int if (80 to 90).contains(x) => "B"
  case x:Int if (70 to 80).contains(x) => "C"
  case x:Int if (60 to 70).contains(x) => "D"
  case x:Int if (0 to 60).contains(x) => "F"
  case x:String if VALID_GRADES(x.toUpperCase) => x.toUpperCase
}

printf("Amy scores %d and receives %s\n", 91, letterGrade(91))
printf("Bob scores %d and receives %s\n", 72, letterGrade(72))
printf("Sam never showed for class, scored %d, and received %s\n", 
    44, letterGrade(44))
printf("Roy transfered and already had %s, which translated as %s\n",
    "B", letterGrade("B"))

リスト 1 では関数の本体すべてが、value に適用される match で構成されています。match の選択肢のそれぞれでは、引数の型に加え、パターン・ガードによる基準に基づいた一致結果のフィルタリングができるようになっています。この構文を使用するメリットは、面倒な if 文を連ねることなく、簡潔に選択肢を区分けできることです。

パターン・マッチングは、Scala の case クラスと連動します。case クラスは、(パターン・マッチングを実行する機能だけでなく) 判別シーケンスを排除する特殊な性質を持つクラスです。例えば、リスト 2 に記載する、配色のマッチングを見てください。

リスト 2. Scala の case クラスをマッチングする
class Color(val red:Int, val green:Int, val blue:Int)

case class Red(r:Int) extends Color(r, 0, 0)
case class Green(g:Int) extends Color(0, g, 0)
case class Blue(b:Int) extends Color(0, 0, b)

def printColor(c:Color) = c match {
  case Red(v) => println("Red: " + v)
  case Green(v) => println("Green: " + v)
  case Blue(v) => println("Blue: " + v)
  case col:Color => {
    print("R: " + col.red + ", ")
    print("G: " + col.green + ", ")
    println("B: " + col.blue)
  }

  case null => println("invalid color")
}

リスト 2 では、基底クラス Color を作成した後、それぞれの色に特化した単一色のバージョンを case クラスとして作成します。どの色が関数に渡されたのかを判別する際には、match を使用して (null に対処する最後の case を含む) すべての考えられる選択肢に対してパターン・マッチングを行います。

Java にはパターン・マッチングがないため、簡潔で読みやすいディスパッチ・コードを作成する Scala の機能を再現することはできません。しかし、Generics とよく知られたデータ構造を結合すれば、それに近いものになります。では、それを実現するために、話を再び Either に戻します。


Either ツリー

ツリー・データ構造は、表 1 に記載する 3 つの抽象化を使用してモデル化することができます。

表 1. ツリーの作成に使用される 3 つの抽象化
Emptyセルに値が含まれない
Leafセルに特定のデータ型の値が 1 つ含まれる
Node他の Leaf または Node を指す

前回の記事では、Either クラスの単純なバージョンを実装しましたが、今回の例では便宜上、Functional Java フレームワーク (「参考文献」を参照) の Either クラスの実装を使用します。概念的には、Either 抽象クラスは必要とされるスロット数に拡張されます。例えば、Either<Empty, Either<Leaf, Node>> という宣言によって、図 2 に示すような 3 つの部分からなるデータ構造が作成されます。

図 2. Either<Empty, Either<Leaf, Node>> のデータ構造
Either の 3 つの部分からなるデータ構造を示す図

3 つのツリー抽象化からなる Either 実装をベースとし、リスト 3 に記載するツリーを定義します。

リスト 3. Either をベースとしたツリー
import fj.data.Either;
import static fj.data.Either.left;
import static fj.data.Either.right;

public abstract class Tree {
    private Tree() {}

    public abstract Either<Empty, Either<Leaf, Node>> toEither();

    public static final class Empty extends Tree {
        public Either<Empty, Either<Leaf, Node>> toEither() {
            return left(this);
        }

        public Empty() {}
    }

    public static final class Leaf extends Tree {
        public final int n;

        public Either<Empty, Either<Leaf, Node>> toEither() {
            return right(Either.<Leaf, Node>left(this));
        }

        public Leaf(int n) { this.n = n; }
    }

    public static final class Node extends Tree {
        public final Tree left;
        public final Tree right;

        public Either<Empty, Either<Leaf, Node>> toEither() {
            return right(Either.<Leaf, Node>right(this));
        }

        public Node(Tree left, Tree right) {
            this.left = left;
            this.right = right;
        }
    }
}

リスト 3 の抽象クラス Tree は、その内部で EmptyLeafNodeという 3 つの final 具象クラスを定義しています。Tree クラスの内部では 3 つのスロットからなる Either (図 2 を参照) を使用して、左端のスロットには常に Empty、中央のスロットには Leaf、右端のスロットには Node を格納するという規約を強制します。その方法は、各クラスに toEither() メソッドを実装させて、そのクラスの型に対応する適切な「スロット」を返させるというものです。データ構造内の各「セル」は、従来のコンピューター・サイエンスで意味するところの共用体であり、3 つの可能な型のうち、常に 1 つだけを格納するように作られています。

このツリー構造を前提として、その内部構造が Either<Empty, Either<Leaf, Node>> をベースとしていることがわかっていれば、ツリー内の各要素を巡回するパターン・マッチングを模倣することができます。


ツリーをトラバースするためのパターン・マッチング

Scala のパターン・マッチングは、個々のケースについて考えられるような仕組みになっています。Functional Java による Either 実装の left() メソッドと right() メソッドは、どちらも Iterable インターフェースを実装します。このインターフェースを使えば、パターン・マッチングから発想を得た、ツリーの深さを判別するためのコードを作成することができます (リスト 4 を参照)。

リスト 4. パターン・マッチング風の構文を使用してツリーの深さをチェックする
static public int depth(Tree t) {
    for (Empty e : t.toEither().left())
        return 0;
    for (Either<Leaf, Node> ln: t.toEither().right()) {
        for (Leaf leaf : ln.left())
            return 1;
        for (Node node : ln.right())
            return 1 + max(depth(node.left), depth(node.right));
    }
    throw new RuntimeException("Inexhaustible pattern match on tree");
}

リスト 4depth() メソッドは、再帰的に深さを調べる関数です。このツリーは特定のデータ構造 (Either<Empty, Either<Leaf, Node>>) をベースとしているため、それぞれの「スロット」を特定のケースとして扱うことができます。セルが空 (Empty) であれば、そのブランチに深さはありません。セルがリーフ (Leaf) であれば、それを 1 ツリー・レベルとしてカウントします。セルがノード (Node) であれば、再帰的に left と right の両方を検索し、再帰的検索によって得られたツリー・レベルに 1 を加えます。

ツリーの再帰的検索を行う場合も、上記と同じパターン・マッチング構文を使用することができます (リスト 5 を参照)。

リスト 5. ツリー内での存在の有無を判別する
static public boolean inTree(Tree t, int value) {
    for (Empty e : t.toEither().left())
        return false;
    for (Either<Leaf, Node> ln: t.toEither().right()) {
        for (Leaf leaf : ln.left())
            return value == leaf.n;
        for (Node node : ln.right())
            return inTree(node.left, value) | inTree(node.right, value);
    }
    return false;
}

前と同じく、データ構造の中に存在する可能性のある各「スロット」に対して戻り値を指定します。空のセルを検出した場合は、false を返します。この場合、検索は失敗したことになります。リーフを検出した場合には、渡された値をチェックし、それが一致すれば true を返します。ノードを検出した場合にはツリーを再帰的に処理し、| (or 非短絡演算子) を使用して、返されたブール値を結合します。

ツリーの作成と検索の実際の動作を確認するには、リスト 6 のユニット・テストを行うことを検討してください。

リスト 6. ツリーで検索できるかどうかをテストする
@Test
public void more_elaborate_searchp_test() {
    Tree t = new Node(new Node(new Node(new Node(
            new Node(new Leaf(4),new Empty()), 
            new Leaf(12)), new Leaf(55)), 
            new Empty()), new Leaf(4));
    assertTrue(inTree(t, 55));
    assertTrue(inTree(t, 4));
    assertTrue(inTree(t, 12));
    assertFalse(inTree(t, 42));
}

リスト 6 では、まずツリーを作成し、続いて要素が存在するかどうかを調べます。inTree() メソッドは、リーフのいずれか 1 つが検索値と同じである場合、true を返します。すると、ノードでの | (or) 演算子により (リスト 5 を参照)、true が再帰呼び出しスタックを伝播します。

リスト 5 の例は、要素がツリー内に出現するかどうかを判別するだけですが、さらに高度なバージョンでは、要素の出現回数までチェックします (リスト 7 を参照)。

リスト 7. ツリー内での要素の出現回数を調べる
static public int occurrencesIn(Tree t, int value) {
    for (Empty e: t.toEither().left())
        return 0;
    for (Either<Leaf, Node> ln: t.toEither().right()) {
        for (Leaf leaf : ln.left())
            if (value == leaf.n) return 1;
        for (Node node : ln.right())
            return occurrencesIn(node.left, value) + occurrencesIn(node.right, value);
    }
    return 0;
}

リスト 7 では、一致するリーフごとに 1 を返すようにしています。そのため、ツリー内に該当するリーフが出現する回数をカウントできるというわけです。

リスト 8 に、複雑なツリーで depth()inTree()occurrencesIn() をテストする例を記載します。

リスト 8. 複雑なツリーで深さ、存在の有無、出現回数をテストする
@Test
public void multi_branch_tree_test() {
    Tree t = new Node(new Node(new Node(new Leaf(4),
            new Node(new Leaf(1), new Node(
                    new Node(new Node(new Node(
            new Node(new Node(new Leaf(10), new Leaf(0)),
                    new Leaf(22)), new Node(new Node(
                            new Node(new Leaf(4), new Empty()),
                            new Leaf(101)), new Leaf(555))),
                            new Leaf(201)), new Leaf(1000)),
                    new Leaf(4)))),
            new Leaf(12)), new Leaf(27));
    assertEquals(12, depth(t));
    assertTrue(inTree(t, 555));
    assertEquals(3, occurrencesIn(t, 4));
}

ツリーの内部構造には規則性をもたせていることから、要素の型に反映された各ケースについて個別に検討することによって、トラバース中にツリーを分析することができます。本格的な Scala のパターン・マッチングほどの表現力ではありませんが、この構文は驚くほど Scala の典型的なパターン・マッチングに近いものになっています。


まとめ

今回の記事では、ツリーの内部構造に規則性を課すことによってツリーのトラバースに Scala スタイルのパターン・マッチングを適用し、Generics に固有のプロパティーである Iterable、Functional Java の Either クラス、そしてその他いくつかの構成要素を組み合わせて強力な Scala の機能を模倣する方法を説明しました。

次回の記事では、Java で使用可能な限られた方法とは対象的に、次世代の Java 言語で使用できるさまざまなメソッド・ディスパッチ・メカニズムについての調査を開始します。

参考文献

学ぶために

製品や技術を入手するために

  • IBM 製品の評価版をダウンロードするか、あるいは IBM SOA Sandbox のオンライン試用版で、DB2、Lotus、Rational、Tivoli、および WebSphere などが提供するアプリケーション開発ツールやミドルウェア製品を試してみてください。

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Java technology
ArticleID=829141
ArticleTitle=関数型の考え方: Either ツリーとパターン・マッチング
publish-date=08092012