Iterableを直接実装しない

概要

コレクションにIterableを実装させる事で、そのコレクションのインスタンスを拡張for文の対象にでき、簡単にイテレート出来るようになります。しかし、IterableではIteratorを返すメソッドを1つしか定義出来ないため、拡張for文によるコレクションの走査順を切り替えることが出来ません。コレクションがIterableを実装する代わりに、そのコレクションに異なる走査順に対応するIterableを返すメソッドを複数個定義するIterableProviderパターンを採用する事でイテレート時の走査順の切り替えが柔軟な設計になります。

イテレート、及びIterableとIteratorの関係

イテレートとは、コレクションからある順番で要素を取り出し、それを用いて次々と副作用を生成する手続きの事を表します。これを抽象化したclass設計の1つがIteratorパターンとしてまとめられており、JavaのIterableとIteratorはIteratorパターン元に定義されているインターフェースです。コレクションを表すclassでIterableを実装し、適切な走査順で値を返すIteratorを用いてiteratorメソッドを実装するのが通常の設計手法です。
JavaにはIteratorパターンによるイテレートを簡単に行うための拡張for文という構文があり、それは次のコードと等価な処理の糖衣構文となっています。

Iterable<T> iterable = ...;
for(Iterator<T> iterator = iterable.iterator(); iterator.hasNext();) {
  T next = iterator.next();
  //nextを用いて副作用を生み出す処理
}

拡張for文ではまずIterableのiteratorメソッドよりIterableの要素を順番に返すIteratorを取得します。続いてIteratorのhasNextメソッドがtrueを返し続ける限りIteratorのnextメソッドを呼び出し続け、副作用を生成し続けます。hasNextがfalseを返すとイテレートは終了し、拡張for文を抜ける仕組みになっています。

Iteratorパターンの問題

Iteratorパターンには拡張for文によるイテレート時の走査順を自由に切り替えられないという問題があります。
一般にコレクションに対しての走査順は複数存在します。Iteratorパターンでは走査順の定義がIteratorの実装に現れており、拡張for文による走査順はIteratorの実装により決まります。しかし拡張for文ではIterableのiteratorメソッドで定義されているIterator以外は利用できません。例えばIterableが複数のメソッドにより異なるIteratorを提供していたとしても、拡張for文ではそれらを使い分ける事が出来ません。従ってコレクションがIterableを実装した場合、拡張for文によるイテレートの走査順は1つに限られてしまいます。
この問題を回避するためには、拡張for文によるイテレート時に使われるIteratorを切り替えられる仕組みが必要になります。

IterableProviderパターン

拡張for文ではイテレートに利用するIteratorを切り替えることは出来ませんが、イテレート対象であるIterableは切り替えることができます。IterableとIteratorはIterableの定義より一対一で対応しているため、拡張for文に渡すIterableを切り替えることはIteratorを切り替える事と等しいです。
これを基に、拡張for文により使われるIteratorを切り替えられるようにするために、IterableProviderパターンという設計手法を提案します。IterableProviderパターンの基本的なアイデアはコレクションとIterableを同一視しない事です。Iteratorの実装にはコレクションの実装が必要ですが、一方でIterableの実装に必要なのはコレクションではありません。あくまで必要なのはIteratorの実装だけです。従ってIterableとコレクションは分離する事が出来ます。Iteratorパターンによる設計手法ではコレクションがIterableを直接実装しますが、[IterableProviderパターン]ではコレクションが走査順に対応するIterableを返すメソッドを複数定義する設計にします。コレクションが提供するそれぞれのIterableは走査順に対応するIteratorを返すように実装します。
このように設計する事で、コレクションのユーザは拡張for文に渡すIterableをコレクションから提供されるIterableの中から選択することにより、求める走査順でイテレートを行うことができます。

二分木に対するIterableProviderパターンの実装

二分木を対象にIterableProviderパターンを実装します。二分木には様々な走査順があり得ますが、ここでは前順、間順、後順の深さ優先探索、及び幅優先探索を実装し、それらを実際に拡張for文で利用する事で走査順が切り替えられることを示します。
実装時に以下のライブラリを利用しています。

なおここで用いるコードはGitHubリポジトリで公開されています。

データ構造

二分木のノードを表すクラスは次のように実装されています。

package raystark.iterablesample;

import org.jetbrains.annotations.NotNull;
import raystark.eflib.option.Option;
import raystark.eflib.option.Option.None;

public final class Node<T> {
    private final T value;
    private final Option<Node<T>> left;
    private final Option<Node<T>> right;

    public Node(@NotNull T value, @NotNull Option<Node<T>> left, @NotNull Option<Node<T>> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node(@NotNull T value) {
        this(value, None.of(), None.of());
    }

    @NotNull public T value() { return value; }
    @NotNull public Option<Node<T>> getLeft() { return left; }
    @NotNull public Option<Node<T>> getRight() { return right; }
}

Nodeはleftとrightの2つの子、及び値valueを持ちます。それぞれの子が存在しない可能性があるため、子のNodeはOption型のフィールドで保持しています。子のNode、及び値はコンストラクタでのみ初期化されます。コンストラクタはvalueと left、rightを全て受け取るものの他、子の存在しないノードを生成するための簡易版も定義されています。

コレクション

IterableProviderパターンの対象となるコレクションである二分木は次のように定義されています。

package raystark.iterablesample;

import org.jetbrains.annotations.NotNull;
import raystark.eflib.option.Option;

public final class BinaryTree<T> {
    private final Option<Node<T>> root;

    private final Iterable<T> preorder;
    private final Iterable<T> inorder;
    private final Iterable<T> postorder;
    private final Iterable<T> breadthFirst;

    public BinaryTree(@NotNull Option<Node<T>> root) {
        this.root = root;
        this.preorder = () -> new PreorderIterator<>(this);
        this.inorder = () -> new InorderIterator<>(this);
        this.postorder = () -> new PostorderIterator<>(this);
        this.breadthFirst = () -> new BreadthFirstIterator<>(this);
    }

    public @NotNull Option<Node<T>> root() {
        return this.root;
    }

    public @NotNull Iterable<T> preorderIterable() {
        return preorder;
    }

    public @NotNull Iterable<T> inorderIterable() {
        return inorder;
    }

    public @NotNull Iterable<T> postorderIterable() {
        return postorder;
    }

    public @NotNull Iterable<T> breadthFirstIterable() {
        return breadthFirst;
    }
}

BinaryTree自体はIterableを実装せず、代わりにコンポジションにより各走査順に対応するIterableをフィールドに保持しています。各Iterableの実装はIteratorの実装にのみ依存しており、コレクション自体には一切依存していません。BinaryTreeには根のノードを取得するrootメソッドが定義されており、後述のIteratorではこれを用いて走査アルゴリズムを実装しています。
Iterableには@FunctionalInterfaceアノテーションが付与されていませんが、iteratorメソッドのみを抽象メソッドとしてもつ関数型インターフェースであるため、ここではラムダ式で実装されています。

Iterator

前順、間順、後順、幅優先探索のそれぞれに対応するIteratorは次のように実装されています。

前順

import raystark.eflib.option.Option;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

//参考 http://n00tc0d3r.blogspot.com/2013/08/implement-iterator-for-binarytree-ii.html
final class PreorderIterator<T> implements Iterator<T> {
    private final Deque<Node<T>> stack;

    PreorderIterator(@NotNull BinaryTree<T> tree) {
        this.stack = new ArrayDeque<>();
        tree.root().ifPresent(stack::push);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public @NotNull T next() {
        return Option.ofNullable(stack.poll())
            .whenPresent(polledNode -> {
                polledNode.getRight().ifPresent(stack::push);
                polledNode.getLeft().ifPresent(stack::push);
            })
            .orElseThrow()
            .value();
    }
}

間順

package raystark.iterablesample;

import org.jetbrains.annotations.NotNull;
import raystark.eflib.option.Option;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

// 参考 http://n00tc0d3r.blogspot.com/2013/08/implement-iterator-for-binarytree-i-in.html
final class InorderIterator<T> implements Iterator<T> {
    private final Deque<Node<T>> stack;

    InorderIterator(@NotNull BinaryTree<T> tree) {
        this.stack = new ArrayDeque<>();
        tree.root().repeatMapWithSideEffect(Node::getLeft, stack::push).ifPresent(stack::push);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public T next() {
        return Option.ofNullable(stack.poll())
            .whenPresent(
                leaf -> leaf.getRight()
                    .repeatMapWithSideEffect(Node::getLeft, stack::push)
                    .ifPresent(stack::push)
            ).orElseThrow()
            .value();
    }
}

後順

package raystark.iterablesample;

import org.jetbrains.annotations.NotNull;
import raystark.eflib.option.Option;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

//参考 http://n00tc0d3r.blogspot.com/2013/08/implement-iterator-for-binarytree-iii.html
final class PostorderIterator<T> implements Iterator<T> {
    private final Deque<Node<T>> stack;

    PostorderIterator(@NotNull BinaryTree<T> tree) {
        this.stack = new ArrayDeque<>();
        tree.root().repeatMapWithSideEffect(this::down, stack::push)
            .ifPresent(stack::push);
    }

    private Option<Node<T>> down(Node<T> node) {
        return node.getLeft().or(node.getRight());
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public T next() {
        return Option.ofNullable(stack.poll())
            .whenPresent(
                leaf -> Option.ofNullable(stack.peek())
                    .filter(parent -> parent.getLeft().anyMatch(leaf))
                    .flatMap(Node::getRight)
                    .repeatMapWithSideEffect(this::down, stack::push)
                    .ifPresent(stack::push)
            )
            .orElseThrow()
            .value();
    }
}

幅優先探索

package raystark.iterablesample;

import org.jetbrains.annotations.NotNull;
import raystark.eflib.option.Option;

import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.Queue;

final class BreadthFirstIterator<T> implements Iterator<T> {
    private final Queue<Node<T>> queue;

    BreadthFirstIterator(@NotNull BinaryTree<T> tree) {
        queue = new ArrayDeque<>();
        tree.root().ifPresent(queue::offer);
    }

    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }

    @Override
    public T next() {
        return Option.ofNullable(queue.poll())
            .whenPresent(polledNode -> {
                polledNode.getLeft().ifPresent(queue::offer);
                polledNode.getRight().ifPresent(queue::offer);
            })
            .orElseThrow()
            .value();
    }
}

各Iteratorはコンストラクタで後述のBinaryTreeを受け取っています。各Iteratorの実装は外部に公開する必要が無いため、package-privateなクラスとして宣言されています。
なお、前順、間順、後順のアルゴリズムの実装はソースコード上のURLの記事を参考にしました。

Main

これらを実際に利用するMainクラスは次のように実装されています。

package raystark.iterablesample;

import raystark.eflib.option.Option.Some;

public class Main {
    public static void main(String[] args) {
        var tree = new BinaryTree<>(
            Some.of(new Node<>(6,
                Some.of(new Node<>(2,
                    Some.of(new Node<>(1)),
                    Some.of(new Node<>(4,
                        Some.of(new Node<>(3)),
                        Some.of(new Node<>(5))
                    ))
                )),
                Some.of(new Node<>(10,
                    Some.of(new Node<>(8,
                        Some.of(new Node<>(7)),
                        Some.of(new Node<>(9))
                    )),
                    Some.of(new Node<>(11))
                ))
            )
        ));

        System.out.println("Preorder");
        for(var value : tree.preorderIterable())
            System.out.print(" " + value);
        System.out.println();

        System.out.println("Inorder");
        for(var value : tree.inorderIterable())
            System.out.print(" " + value);
        System.out.println();

        System.out.println("Postorder");
        for(var value : tree.postorderIterable())
            System.out.print(" " + value);
        System.out.println();

        System.out.println("BreathFirst");
        for(var value : tree.breadthFirstIterable())
            System.out.print(" " + value);
        System.out.println();
    }
}

最初に二分木を構築し、その二分木が提供するIterableをそれぞれ拡張for文に渡して標準出力に出力しています。
二分木の構造は次のようになっています。

      6
    /   \
   2     10
  / \   /  \
 1   4  8   11
   / |  | \
  3  5  7  9

実行例

Mainの実行例を示します。

Preorder
 6 2 1 4 3 5 10 8 7 9 11
Inorder
 1 2 3 4 5 6 7 8 9 10 11
Postorder
 1 3 5 4 2 7 9 8 11 10 6
BreathFirst
 6 2 10 1 4 8 11 3 5 7 9

IterableProviderパターンを採用する事で、拡張for文で同じコレクションに対する複数の走査順によるイテレートが出来る事が確認できます。

考察

IterableProviderに対する走査順の追加

Iteratorパターンではコレクションに対する走査順が1つに限られるため、新たな走査順を追加することが出来ません。しかしIterableProviderパターンでは提供されるIterableが1つとは限らない上にそれぞれのIterable及びIteratorはIterableProviderに対して独立して実装されます。従ってコレクションに対しては新たな走査順に対応するIterableを返すメソッドを後から自由に行うことができます。この拡張性の高さはIteratorパターンには無い利点です。

IterableProviderパターンの他の実装方法

二分木に対するIterableProviderパターンの実装ではIteratorを外部で定義し、IterbleProviderが提供するIterableをフィールドに保持していました。つまりIterableProviderはデータ構造と複数のIterableからなるコンポジションでした。コンポジションによる実装の他に内部クラスを利用する方針が考えられます。つまりIterableProviderがIterableを非staticな内部クラスとして定義する方針です。この方針の場合IterableProviderを実装するclassの定義にIterable及びIteratorの定義が現れるためIterableProviderのコードが長大になる可能性があります。簡易な実装で済むのであれば良いですが、拡張すればするほどソースコードが膨れ上がる事を留意する必要があります。その代わりIteratorの実装をパッケージに対して隠蔽出来る利点があります。

IterableProviderに対応する型

IterableProviderパターンではIterableProviderに対応する型の定義が難しいです。IteratorパターンではIterableが提供するIteratorが1つに定まっていましたが、IterableProviderパターンではIterableProviderが提供するIterableが一つに定まっていません。更にそれらのIterableはイテレート順が区別できるように名前が付けられなければならないため、単純にIterableのコレクションを返すわけにもいきません。IterableProviderが返すIterableの実装はコレクションに依存しているため、IterableProviderパターンはコレクションで実装する他ありませんが、そのコレクションがIterableProviderパターンで実装されている事を型で証明する事は出来ません。

IterableProviderパターンとIteratorパターンの組み合わせ

コレクションをIteratorパターンで実装した場合、コレクション自身がIterableとなり、インスタンスを直接拡張for文に渡すことが出来ます。仮にIteratorパターンで実装されたコレクションがIterableProviderパターンを実装した場合2つのパターンはどのように関係するのでしょうか。
この場合ユーザーがコレクションに対するイテレートを行う際にコレクション自身を拡張for文に渡す方法とコレクションの返すIterableを拡張for文に渡す方法の何れかを選ぶことができます。この時IteableProviderパターンでは[Iteable]に走査順を表す名前を付けられるのに対してコレクション自身には走査順を表す名前を付けることが出来ません。
私はコレクション自身を拡張for文に渡すことは、自然な走査順によりイテレートを行う事だと考えます。例えば配列やリストであれば添字の昇順、順序付きデータ構造であれば順序の昇順等特に違和感無く利用できる走査順です。
IteratorパターンとIterableProviderパターンの組み合わせによる自然な走査順の定義は便利ではありますが、その走査順が本当に自然か否かについては議論の余地があります。例えば二分木に対する間順走査は自明な走査でしょうか、あるいは前順、後順が自然な走査順なのでしょうか。私は機能の一方がデフォルト、他方がオプションという設計はユーザーにどの機能がデフォルトなのかを常に考えさせる負荷を与えるため好ましくないと考えます。従ってIterableProviderパターンとIteratorパターンの組み合わせは避けるべきと考えます。しかしながら適切なデフォルト動作というのは多くの場合記述量が少なくなるという点では便利です。IterableProviderパターンとIteratorパターンを組み合わせる場合はどの走査順がデフォルトなのか、他にどのような走査順が定義されているのかをコレクションのドキュメントで明記すべきです。

結論

IteralbeProviderパターンを採用する事で、コレクションが複数の走査順を提供できるようになり、ユーザはそれらから適切な走査順を選ぶことが出来るようになります。更にIterableProviderパターンは拡張性に優れており、コレクションに対して後から走査順を追加することも可能になります。しかしながらそのコレクションがIterableProviderパターンで実装されている事を型で示す事は難しいため、実装者はその事についてドキュメントで触れるべきです。

ロジニキ雑記

マイクラ、プログラミング等雑記