Javaで学ぶ関数型データ構造（List)
Purely Functional Data Structuresを買って読み始めた。理解を深めるため、無理やりJavaで実装してみることにする。
この本では最初にStackが出てくるんだけど、pushもpopも無い。で、これはいわゆるStackじゃなくて、順番にデータが並んだものを表すのだと注釈がある。なるほどと思いながらも違和感があるので、今回はSeqという名前に変えてしまった。
package com.ruimo.immutable;
public interface Seq {
<E> Elem<E> empty();
<E> boolean isEmpty(Elem<E> e);
<E, E2 extends E> Elem<E> cons(E head, Elem<E2> tail);
<E, E2 extends E> Elem<E> cons(Elem<E> former, Elem<E2> latter);
<E> E head(Elem<E> e);
<E> Elem<E> tail(Elem<E> e);
<E, E2 extends E> Elem<E> update(Elem<E2> target, int idx, E value);
<E> Elem<E> cast(Elem<? extends E> e);
}
Javaでは配列はCovariantだけど、コレクションはInvariant。つまり親の型を要素とするコレクションの参照変数で、子の型を要素とするコレクションを参照できない。今回はImmutableなデータ構造なのでCovariantにできるのだけど、Javaのジェネリクスにはそれを伝える方法が無いんで、cast()メソッドを用意してみた。
Elemは、要素の型でおなじみの、NilとCons。
package com.ruimo.immutable;
public interface Elem<E> {
void visit(ElementVisitor<E> visitor);
}
package com.ruimo.immutable;
package com.ruimo.immutable;
class Nil implements Elem<Object> {
Nil() {}
@Override public void visit(ElementVisitor<Object> visitor) {
visitor.onNil(this);
}
static final Elem<Object> NIL = new Nil();
@SuppressWarnings("unchecked")
static <E> Elem<E> nil() {
return (Elem<E>)NIL; // unchecked warning.
}
}
package com.ruimo.immutable;
class Cons<E, E2 extends E> implements Elem<E> {
final E head;
final Elem<E2> tail;
Cons(E head, Elem<E2> tail) {
if (head == null) throw new NullPointerException("head is null.");
if (tail == null) throw new NullPointerException("tail is null.");
this.head = head;
this.tail = tail;
}
static <E, E2 extends E> Cons<E, E2> cons(E head, Elem<E2> tail) {
return new Cons<E, E2>(head, tail);
}
@Override public void visit(ElementVisitor<E> visitor) {
visitor.onCons(this);
}
}
package com.ruimo.immutable;
public interface ElementVisitor<E> {
void onNil(Nil nil);
<E2 extends E> void onCons(Cons<E, E2> cons);
}
NilとConsを区別して処理する時のためにVisitorを用意。Consはhead側とtail側との型を別に持つようにしてみた。で、いよいよリスト。
package com.ruimo.immutable;
public class ImList implements Seq {
static final ImList theInstance = new ImList();
public static ImList getInstance() {
return theInstance;
}
ImList() {}
public <E> Elem<E> empty() {return Nil.nil();}
public <E> boolean isEmpty(Elem<E> e) {
final boolean[] ret = new boolean[1];
e.visit(new ElementVisitor<E>() {
@Override public void onNil(Nil nil) {
ret[0] = true;
}
@Override public <E2 extends E> void onCons(Cons<E, E2> cons) {
ret[0] = false;
}
});
return ret[0];
}
public <E, E2 extends E> Elem<E> cons(E head, Elem<E2> tail) {
return Cons.cons(head, tail);
}
@SuppressWarnings("unchecked")
public <E, E2 extends E> Elem<E> cons(Elem<E> former, Elem<E2> latter) {
if (isEmpty(former)) return (Elem<E>)latter; // unchecked warning.
else return cons(head(former), cons(tail(former), latter));
}
@SuppressWarnings("unchecked")
public <E> E head(Elem<E> e) {
final Object[] ret = new Object[1];
e.visit(new ElementVisitor<E>() {
@Override public void onNil(Nil nil) {
throw new EmptyException();
}
@Override public <E2 extends E> void onCons(Cons<E, E2> cons) {
ret[0] = cons.head;
}
});
return (E)ret[0]; // unchecked warning.
}
@SuppressWarnings("unchecked")
public <E> Elem<E> tail(Elem<E> e) {
final Object[] ret = new Object[1];
e.visit(new ElementVisitor<E>() {
@Override public void onNil(Nil nil) {
throw new EmptyException();
}
@Override public <E2 extends E> void onCons(Cons<E, E2> cons) {
ret[0] = cons.tail;
}
});
return (Elem<E>)ret[0]; // unchecked warning.
}
@SuppressWarnings("unchecked")
public <E, E2 extends E> Elem<E> update(Elem<E2> target, final int idx, final E value) {
final Object[] ret = new Object[1];
target.visit(new ElementVisitor<E2>() {
@Override public void onNil(Nil nil) {
throw new SubscriptException();
}
@Override public <E3 extends E2> void onCons(Cons<E2, E3> cons) {
if (idx == 0) ret[0] = ImList.this.cons(value, cons.tail);
else ret[0] = ImList.this.cons
((E)cons.head,
ImList.this.<E, E3>update(cons.tail, idx - 1, value));
}
});
return (Elem<E>)ret[0]; // unchecked warning.
}
@SuppressWarnings("unchecked")
public <E> Elem<E> cast(Elem<? extends E> e) {
return (Elem<E>)e; // unchecked warning.
}
}
通常は、リスト型がデータを保持するように実装するのだろうけど、本に習ってリスト型は関数を提供するだけにしてみた。しかしジェネリクスは難しいな。多分もっとスマートに書く方法もあるんだろうが、今の自分にはこのあたりが精一杯。効率は度外視。本来ならビジターはThreadLocalに置いて使い回したりしたいところ。それではテスト。
package com.ruimo.immutable;
import static org.junit.Assert.*;
import org.junit.Test;
public class ImListTest {
ImList list = ImList.getInstance();
@Test public void empty() throws Exception {
Elem<Integer> nil = list.empty();
assertTrue(list.isEmpty(nil));
}
@Test public void one() throws Exception {
Elem<Integer> nil = list.empty();
Elem<Integer> e1 = list.cons(1, nil);
assertEquals(Integer.valueOf(1), list.head(e1));
assertEquals(nil, list.tail(e1));
}
@Test public void two() throws Exception {
Elem<Integer> nil = list.empty();
Elem<Integer> e1 = list.cons(1, nil);
Elem<Integer> e2 = list.cons(2, e1);
assertEquals(Integer.valueOf(2), list.head(e2));
assertEquals(e1, list.tail(e2));
}
@Test public void differentTypes() throws Exception {
Elem<Integer> e1 = list.cons(1, list.<Integer>empty());
Elem<Number> e2 = list.cons((Number)1.2d, e1);
assertEquals(Double.valueOf(1.2d), list.head(e2));
assertEquals(Integer.valueOf(1), list.head(list.tail(e2)));
}
@Test public void cons() throws Exception {
Elem<Integer> i1 = list.cons(1, list.cons(2, list.<Integer>empty()));
Elem<Double> d1 = list.cons(0.2d, list.<Double>empty());
Elem<Number> n1 = list.cons(list.<Number>cast(d1), i1);
assertEquals(Double.valueOf(0.2d), list.head(n1));
assertEquals(Integer.valueOf(1), list.head(list.tail(n1)));
}
@Test public void update() throws Exception {
Elem<Integer> i1 = list.cons(1, list.cons(2, list.<Integer>empty()));
Elem<Integer> i2 = list.update(i1, 0, 100);
assertEquals(Integer.valueOf(100), list.head(i2));
assertEquals(Integer.valueOf(2), list.head(list.tail(i2)));
Elem<Integer> i3 = list.update(i2, 1, 200);
assertEquals(Integer.valueOf(100), list.head(i3));
assertEquals(Integer.valueOf(200), list.head(list.tail(i3)));
}
@Test public void updateDifferentType() throws Exception {
Elem<Integer> i1 = list.cons(1, list.cons(2, list.<Integer>empty()));
Elem<Number> n2 = list.update(i1, 0, (Number)100d);
assertEquals(Double.valueOf(100d), list.head(n2));
assertEquals(Integer.valueOf(2), list.head(list.tail(n2)));
Elem<Number> n3 = list.update(n2, 1, (Number)200d);
assertEquals(Double.valueOf(100d), list.head(n3));
assertEquals(Double.valueOf(200d), list.head(list.tail(n3)));
}
}
Covariantにしたんで、Integerのリストの前に、Doubleのリストを連結したり(結果はIntegerとDoubleの共通の親型であるNumberのリスト)、Integerのリストの要素をDoubleで置きかえたり(結果は、やはりNumebrのリスト)とかできる。けど、その分複雑になってしまった感がある。Elem<Integer>とElem<Double>を受けとったら、自動的に戻りがElem<Number>になったりするメソッドが作成できると、もっと自然になりそうだけど、多分Javaのジェネリクスでは無理だよね？
public class Test {
static <T, T2 extends T, T3 extends T> T foo(T2 t2, T3 t3) {
return null;
}
static void bar() {
Number n = Test.<Number, Integer, Double>foo(1, 1.2d);
}
}
と明示的に書けばコンパイルできるけど、
static void bar() {
Number n = Test.foo(1, 1.2d);
}
だと、さすがに型を推論とかはしてくれない。
shanai@shanai-desktop:/tmp$ javac Test.java
Test.java:7: 内部エラーです。
というか、エラーメッセージが意味不明。「イン」って何だろう？ 「インファーできません」とかかなぁ。
つづく、かもしれない。
