Mirko Rahn wrote:
Note that the signatures of mirror and rel are the same as before. Try
this in your favorite language!
It's easy to encode this in some object oriented language with generics,
like Java. (But no, Java is not my favorite language).
Let's add a general pair type to stay close to the haskell way of
encoding data.
class Pair {
public final A fst;
public final B snd;
public Pair(A fst, B snd) {
this.fst = fst;
this.snd = snd;
}
public Pair swap() {
return new Pair(snd, fst);
}
}
Using the standard List type and this Pair type, we can easily encode a
Rel type wich naively computes new mirrors every time mirror is used.
class Rel<Q> {
private final List> xs;
public Rel(List> xs) {
this.xs = xs;
}
public Rel<Q> mirror() {
return new Rel<Q>(mirrorList(xs));
}
public static <Q> List> mirrorList(List> xs) {
List> ys = new ListOfYourChoice>();
for (Pair x : xs)
ys.add(x.swap());
return ys;
}
}
By subclassing, we can specialize this to precompute the mirror and
build a cyclic data structure like in the haskell example:
class MirrorRel<Q> extends Rel<Q> {
private final Rel<Q> mirror;
public MirrorRel(List> xs) {
super(xs);
this.mirror = new MirrorRel<Q>(mirrorList(xs), this);
}
public MirrorRel(List> xs, Rel<Q> mirror) {
super(xs);
this.mirror = mirror;
}
public Rel<Q> mirror() {
return mirror;
}
}
Note that we don't have to change a single line of code in the
definition of Rel to make MirrorRel work, and due to subtyping, we can
use MirrorRel everywhere we used to use Rel, including compiled code.
But this is different from the haskell example because it creates the
mirror eagerly, not lazily. Let's change this by manually wrapping the
construction of the mirror in a thunk.
abstract class Thunk<T> {
private T value;
private boolean evaluated = false;
protected abstract T evaluate();
public T force() {
if (!evaluated) {
value = evaluate();
evaluated = true;
}
return value;
}
}
class LazyMirrorRel<Q> extends Rel<Q> {
private final Thunk mirror;
public LazyMirrorRel(final List> xs) {
super(xs);
final LazyMirrorRel<Q> mirrorsMirror = this;
this.mirror = new Thunk() {
protected Rel<Q> evaluate() {
return new MirrorRel<Q>(mirrorList(xs), mirrorsMirror);
}
};
}
public Rel<Q> mirror() {
return mirror.force();
}
}
The haskell solution may be much shorter, but it is far from impossible
to encode such things in a plain-and-boring mainstream language like
java. The promotional value of this (and similar) examples shrinks down
to "haskell code is much shorter". Wich is true, and important, but may
not be enough to consider learning some crazy programming language.
(Java developers who don't understand Java's advanced features like
generics and anonymous classes may not be able to write or understand
the above written Java solution; but do you expect them to understand
Haskell?)
Tillmann
