Main.hs

data Lit = Lit Int
data Add l r = Add l r

class Eval x where
  eval :: x -> Int

instance Eval Lit where
  eval (Lit x) = x

instance (Eval l, Eval r) => Eval (Add l r) where
  eval (Add l r) = eval l + eval r

class PPrint x where
  pprint :: x -> String

instance PPrint Lit where
  pprint (Lit x) = show x

instance (PPrint l, PPrint r) => PPrint (Add l r) where
  pprint (Add l r) = "(" ++ pprint l ++ " + " ++ pprint r ++ ")"

data Mult l r = Mult l r

instance (Eval l, Eval r) => Eval (Mult l r) where
  eval (Mult l r) = eval l * eval r

instance (PPrint l, PPrint r) => PPrint (Mult l r) where
  pprint (Mult l r) = pprint l ++ " * " ++ pprint r

threePlus5 = Add (Lit 3) (Lit 5)
threePlus5Times7 = Mult threePlus5 (Lit 7)

main = do
  putStrLn $ pprint threePlus5 ++ " = " ++ show (eval threePlus5)
  putStrLn $ pprint threePlus5Times7 ++ " = " ++ show (eval threePlus5Times7)

Main.java

interface Alg1<E> {
    E lit(int x);
    E add(E l, E r);
}

interface Eval {
    int eval();
}

class ELit implements Eval {
    int x;
    public ELit(int x) { this.x = x; }
    public int eval() { return x; }
}

class EAdd implements Eval {
    private Eval l, r;
    public EAdd(Eval l, Eval r) { this.l = l; this.r = r; }
    public int eval() { return l.eval() + r.eval(); }
}

class Alg1EvalFactory implements Alg1<Eval> {
    public Eval lit(int x) { return new ELit(x); }
    public Eval add(Eval l, Eval r) { return new EAdd(l, r); }
}

class Impl1<E> {
    public static <E> E make3Plus5(Alg1<E> f) {
        return f.add(f.lit(3), f.lit(5));
    }
}

class Impl2 {
    static int eval3Plus5() {
        return Impl1.make3Plus5(new Alg1EvalFactory()).eval();
    }
}

interface Print {
    public String print();
}

class PLit implements Print {
    private int x;
    public PLit(int x) { this.x = x; }
    public String print() { return Integer.valueOf(x).toString(); }
}

class PAdd implements Print {
    private Print l, r;
    public PAdd(Print l, Print r) { this.l = l; this.r = r; }
    public String print() { return "(" + l.print() + " + " + r.print() + ")"; }
}

class Alg1PrintFactory implements Alg1<Print> {
    public Print lit(int x) { return new PLit(x); }
    public Print add(Print l, Print r) { return new PAdd(l, r); }
}

class Impl3 {
    // a client program using the above algebra
    static String print3Plus5() {
        return Impl1.make3Plus5(new Alg1PrintFactory()).print();
    }
}

interface Alg2<E> extends Alg1<E> {
    E mult(E l, E r);
}

class EMult implements Eval {
    private Eval l, r;
    public EMult(Eval l, Eval r) { this.l = l; this.r = r; }
    public int eval() { return l.eval() * r.eval(); }
}

class PMult implements Print {
    private Print l, r;
    public PMult(Print l, Print r) { this.l = l; this.r = r; }
    public String print() { return l.print() + " * " + r.print(); }
}

class Alg2EvalFactory extends Alg1EvalFactory implements Alg2<Eval> {
    public Eval mult(Eval l, Eval r) { return new EMult(l, r); }
}

class Alg2PrintFactory extends Alg1PrintFactory implements Alg2<Print> {
    public Print mult(Print l, Print r) { return new PMult(l, r); }
}

class Impl4<E> {
    // a client program using Alg2 (which uses a function using Alg1!)
    public static <E> E make3Plus5Times7(Alg2<E> f) {
        return f.mult(Impl1.make3Plus5(f), f.lit(7));
    }

    public static int eval3Plus5Times7() {
        return make3Plus5Times7(new Alg2EvalFactory()).eval();
    }

    public static String print3Plus5Times7() {
        return make3Plus5Times7(new Alg2PrintFactory()).print();
    }
}

public class Main {
    public static void main(String[] args)
    {
        System.out.println(Impl3.print3Plus5() + " = " + Integer.valueOf(Impl2.eval3Plus5()).toString());
        System.out.println(Impl4.print3Plus5Times7() + " = " + Integer.valueOf(Impl4.eval3Plus5Times7()).toString());
    }
}

What is the license of the code? Would you mind if I include this examples in my personal collection of functional recipes (github.com/rizo/lambda-lab)? I'll keep the reference to this gist and to your original blog post, of course.

And btw, thanks for the great post and smart solutions both in Haskell in Java! ;)