Haskell datatype to Java(OO)

Question

I'm trying to convert a simple Haskell datatype and a function to OO. But I'm confused..

Have the following Haskell type for arithmetic calculation:

data Expr = Lit Int | 
      Add Expr Expr |
   deriving Show

--Turn the expr to a nice string
showExpr :: Expr -> String 
showExpr (Lit n) = show n
showExpr (Add e1 e2) = "(" ++ showExpr e1 ++ "+" ++ showExpr e2 ++ ")"

Now I'm trying to convert..

public interface Expr {
  String showExpr(String n);
} 

// Base case
public class Lit implements Expr {
  String n;

  public Lit(String n) {
    this.n = n;
  }

  @Override
  public String ShowExpr() {
    return n;
  }
}

public class Add implements Expr {
  Expr a;
  Expr b;

  public Add(Expr aExpr, Expr bExpr) {
    this.a = aExpr;
    this.b = bExpr;
  }

  public String ShowExpr() {
    return "(" + a.ShowExpr() + "+" + b.ShowExpr() + ")";
  }

  public static void main(String[] args) {
    Lit firstLit  = new Lit("2");
    Lit secLit = new Lit("3");
    Add add = new Add(firstLit,secLit);
    System.out.println(add.ShowExpr());
  }
}

This will result in "(2+3)", it's correct answer.

But.. I'm not sure.. is this the right way to think about it and model it in OO ?

Is't a good representation of the Haskell datatype ?

Answer 1

Let's copy the code as closely as we can.

Here are some properties that the Haskell data structure has:

1. It has the type Expr and two constructors Lit and Add
2. You cannot add or remove constructors from the "outside"

So, if we want these properties to stay true in the Java version, you should do it like this:

public abstract class Expr {
    // So that you can't add more subclasses outside this block
    private Expr() {}

    // Simulate pattern matching:
    // (This CAN be done with instanceof, but that's ugly and not OO)
    public boolean isLit() {
        return false;
    }
    public boolean isAdd() {
        return false;
    }
    public Lit asLit() {
        throw new UnsupportedOperationException("This is not a Lit");
    }
    public Add asAdd() {
        throw new UnsupportedOperationException("This is not an Add");
    }

    public static class Lit extends Expr {
        public final int n;
        public Lit(int n) {
            this.n = n;
        }
        @Override
        public boolean isLit() {
            return true;
        }
        @Override
        public Lit asLit() {
            return this;
        }
    }

    public static class Add extends Expr {
        public final Expr a, b;
        public Lit(Expr a, Expr b) {
            this.a = a;
            this.b = b;
        }
        @Override
        public boolean isAdd() {
            return true;
        }
        @Override
        public Add asAdd() {
            return this;
        }
    }
}

Now, to convert showExpr:

public static String showExpr(final Expr expr) {
    if(expr.isLit()) {
        return Integer.toString(expr.asLit().n);
    } else if(expr.isAdd()) {
        return "(" + expr.asAdd().a + "+" + expr.asAdd().b + ")";
    }
}

You can put showExpr as a static method in the Expr class. I would not make it an instance method, because that strays further from the Haskell version.

Answer 2

I would slightly turn this on its head: each Haskell class becomes a Java interface, and instance ...where (or derives) becomes implements.

So, class Show a becomes

interface Showable {
    String show();
}

Now then, what does the Expr data type do? It combines various Haskell constructors -- aka Java classes -- into a single type, and also says they all are covered by Haskell classes (ie implement Java interfaces). So, I would then say that the data type Expr becomes

interface Expr extends Showable {}

and the Lit constructor, for instance, becomes:

class Lit implements Expr {
    @Override
    String show() {
        ...
    }
}

Now you can have Java collections that include both Lit and Add instances (e.g. List<Expr>), and for any Expr, you know it implements Showable.

Note that by pulling Showable as its own interface (rather than putting its method directly on Expr as you did), I allow other, completely unrelated Java classes to also implement it. This is akin to how anybody can define an instance ... where of any Haskell class you define.

Finally, there's a couple mismatches between open-world and closed-world policies here. Haskell's instance ... where is open-world, whereas Java's implements is closed. But Haskell's constructors-per-type is closed, whereas Java's extends is mostly open.

There's not much you can do about implements being closed, but you can close the extends with an abstract class and a private constructor, so that's what I would do (if you want that behavior). Tweaking the above a bit, we get:

public abstract class Expr implements Showable {
    private Expr() {
        // hide the ctor from the outside world, so nobody else
        // can extend this class
    }

    public static class Lit extends Expr {
        ...
    }

    public static class Add extends Expr {
        ...
    }
}

Answer 3

I would translate it that way:

public abstract class Expr {

    public static Expr Lit(final int n) {
        return new Expr() {
            public String showExpr() {
                return "" + n;
            }
        };
    }

    public static Expr Add(final Expr e1, final Expr e2) {
        return new Expr() {
            public String showExpr() {
                return String.format("(%s+%s)", e1.showExpr(), e2.showExpr());
            }
        };
    }

    public abstract String showExpr();

    public static void main(String[] args) {
        Expr firstLit = Lit(2);
        Expr secLit = Lit(3);
        Expr add = Add(firstLit, secLit);
        System.out.println(add.showExpr());
    }
}

In Haskell Lit and Add are no subtypes (there is no such thing in Haskell) but just Expressions. There is no need to expose the subclasses in Java, which I why I could use anonymous classes hidden in some methods. This works perfect, as long as you don't need pattern matching (which is hard to model in Java anyway, as the simple instanceof test gets soon messy with more complicated examples).

Answer 4

Your code looks fine, but could be a little more idiomatic. You can use final to make fields immutable, for example. You might as well replace showExp with toString (which is declared in Object), unless you want toString to do something different. Using String.format is a little cleaner than concatenating several strings, in my opinion. Finally, I would have Lit store an int, since it's more compact and type safe.

Here's how I would translate it:

abstract class Exp {
  // Force subclasses to override Object.toString.
  public abstract String toString();
}

class Lit extends Exp {
  final int value;

  Lit(int value) {
    this.value = value;
  }

  public String toString() {
    return Integer.toString(value);
  }
}

class Add extends Exp {
  final Exp a, b;

  Add(Exp a, Exp b) {
    this.a = a;
    this.b = b;
  }

  public String toString() {
    return String.format("(%s + %s)", a, b);
  }
}

class Main {
  public static void main(String[] args) {
    Lit firstLit = new Lit(2);
    Lit secLit = new Lit(3);
    Add add = new Add(firstLit, secLit);
    System.out.println(add);
  }
}