TL;DR

JDK(tools.jar)中、com.sunパッケージ配下に、javacが内部的に使っている「com.sun.tools.javac.util.List 」が含まれており、これは不変データ構造としてのリストのように(Cons セルベースのリストのように)利用できる。

はじめに

ScalaのコードをGroovyやJavaなどに移植する際に、いつも悲しい思いをするのが不変データ構造に基づいたリスト処理ライブラリが見あたらない、ということでした。JDKの標準コレクションライブラリには、Scalaのscala.collection.immutable.Listのような、不変データ構造を用いて実装されているリストがありません。

ここで言う不変データ構造に基づいたリストとは、JDKのjava.util.Collections.unmodifiableList()等で取得できるような変更禁止ビュー、つまり「要素追加などを禁止するバージョンのリスト」のことではなく、あるいはGrooovyの@Immutableによるイミュータブル指定でもなく、

「要素の追加は可能だが、その意味は、元のリストの変更ではなく、要素が追加された新しいリストを返す」

というもので、さらに実装として「リストを丸ごとコピーして追加して返す」のではなく、「追加前のリストと実体を共有することによって、メモリ利用効率を下げない(そして追加前のリストは不変であることも保証される)」ことが期待されます。もう少しぶっちゃけて言えば、Lispの「ConsセルベースのList」が欲しいのです*1。

もちろん、サードパーティ製のものもあるにはあるでしょう。Functional javaのとか、Clojureのを使うとかはできるのかな。しかし基本的にはやみくもには外部依存を増やしたくはないものです。自分で作りたくもない。

com.sun.tools.javac.util.List

最近知ったのですが、少なくともjava8までのJDKには、com.sunパッケージ配下に「com.sun.tools.javac.util.List 」というクラスがあり、これがまさに求めるものです。ただし、com.sunパッケージにあることから判るように標準APIの一部ではなく、将来的に使える保証はありません。もし使う場合は、将来使えなくなるリスクを覚悟して使う必要があります。さらに、rt.jarではなくtools.jarに含まれているので、JREとしては使用できずJDKの元で使えるものです。javaコマンドから利用する場合、tools.jarをクラスパスに指定することが必要となるでしょう。

※ @kmizuさんにご指摘いただきましたが、これはコメントに記載があるようにGJCつまりGeneric Java Compiler由来のもので、確かこれはScalaのMartin Oderskyさんの関わっていたプロジェクトではないですか。ある意味ご縁があるわけです。

@uehaj なるほどー。知らなったのですが、"List is the main container class in GJC. Most data structures and algorthms in GJC use lists rather than arrays."

2016-04-04 18:00:11 via Twitter Web Client to @uehaj

使い方

com.sun.tools.javac.util.Listの機能としてはこんな感じ。

意味(適当な表記)	書き方
nil	List.nil()
car(a)	a.head
cdr(a)	a.tail
cons(a,b)	b.prepend(a)
[a,b,c]	List.of(a,b,c)

使用例

これを使えば、例えば2リストキューを用いた非破壊的キューもほらこのとおり(cf.20分でわかるPurely Functional Data Structures)。

import com.sun.tools.javac.util.List;
import java.util.function.*;

public class Queue<E> {
    public static class Tuple<E> {
        E value;
        Queue<E> queue;
        Tuple(E value, Queue<E> queue) {
            this.value = value;
            this.queue = queue;
        }
    }

    private List<E> front;
    private List<E> rear;

    public Queue(List<E> front, List<E> rear) {
        this.front = front;
        this.rear = rear;
    }
    public Queue() {
        this(List.nil(), List.nil());
    }

    long size() { return front.size() + rear.size(); }

    public String toString(){ return "front<"+front+rear.reverse()+">rear"; }

    public Queue<E> add(E e) {
        return new Queue<E>(front, rear.prepend(e));
    }
    public Tuple<E> remove() {
        if (front == List.nil()) {
            if (rear == List.nil()) {
                return new Tuple<E>(null, this);
            }
            return new Queue<E>(rear.reverse(), List.nil()).remove();
        }
        else {
            return new Tuple<E>(front.head, new Queue<E>(front.tail, rear));
        }
    }
}

Groovyでさらに

Groovyでは以下の点で使いやすいです。

tools.jarは標準でGroovy実行時のパスに入っている
名前のかぶるListではなく、「import com.sun.tools.javac.util.List as ConsList」のようにリネームしてインポートできる。

なお、残念ながらGroovyでは右結合の演算子をオーバーロードできないので、ScalaやHaskellの::のようにカッコなしで要素繋げる表記を使用することはできません(AST変換を使わないかぎり)。

もっと、もっと…欲しいんじゃっ…!

連想リストのマップっぽく使えるようした物が欲しいですが、それは見つけられませんでした(実装するのはたぶん難しくない)。

Purely Functional Data Structures

posted with amazlet at 16.05.25

Chris Okasaki
Cambridge University Press
売り上げランキング: 50,281

Amazon.co.jpで詳細を見る

Purely Functional Data Structures

posted with amazlet at 16.05.25

Chris Okasaki
Cambridge University Press
売り上げランキング: 242,093

Amazon.co.jpで詳細を見る

*1:LispのListが実際に不変であるか、といえば、実はそうではない。rplaca/rplacdといった破壊的操作があるから。以下で紹介するjavac.tools.Listも同じ。だとすると「不変データ構造と呼ぶべきか」が怪しいといういか間違い。本稿では「不変データ構造のように使えるリスト」として記載。(本件、@yasushia さんにもご指摘いただきました。ありがとうございます。)