[Haskell-cafe] How Albus Dumbledore would sell Haskell

Tillmann Rendel rendel at rbg.informatik.tu-darmstadt.de
Thu Apr 19 20:28:41 EDT 2007


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<A, B> {
   public final A fst;
   public final B snd;

   public Pair(A fst, B snd) {
     this.fst = fst;
     this.snd = snd;
   }

   public Pair<B, A> swap() {
     return new Pair<B, A>(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<Pair<Q,Q>> xs;

   public Rel(List<Pair<Q,Q>> xs) {
     this.xs = xs;
   }

   public Rel<Q> mirror() {
     return new Rel<Q>(mirrorList(xs));
   }

   public static <Q> List<Pair<Q,Q>> mirrorList(List<Pair<Q,Q>> xs) {
     List<Pair<Q,Q>> ys = new ListOfYourChoice<Pair<Q,Q>>();

     for (Pair<Q,Q> 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<Pair<Q,Q>> xs) {
     super(xs);

     this.mirror = new MirrorRel<Q>(mirrorList(xs), this);
   }

   public MirrorRel(List<Pair<Q,Q>> 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<Rel<Q>> mirror;

   public LazyMirrorRel(final List<Pair<Q,Q>> xs) {
     super(xs);

     final LazyMirrorRel<Q> mirrorsMirror = this;

     this.mirror = new Thunk<Rel<Q>>() {
       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


More information about the Haskell-Cafe mailing list