uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかReactとかFregeとかJavaとか -

Javaにも不変データ構造に基づいた(Cons セルベースの)リストがあるのだよ

TL;DR

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

はじめに

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

ここで言う不変データ構造に基づいたリストとは、JDKjava.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さんの関わっていたプロジェクトではないですか。ある意味ご縁があるわけです。

使い方

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では右結合の演算子オーバーロードできないので、ScalaHaskellの::のようにカッコなしで要素繋げる表記を使用することはできません(AST変換を使わないかぎり)。

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

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

Purely Functional Data Structures
Chris Okasaki
Cambridge University Press
売り上げランキング: 50,281
Purely Functional Data Structures
Chris Okasaki
Cambridge University Press
売り上げランキング: 242,093

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