Other answers have covered a more idiomatic way of implementing this in Java, and described how to use Optional to handle errors. But here I’d like to give the direct equivalent of Haskell pattern matching in Java, with the visitor pattern:
public class ExprTest {
public static void main(String[] arguments) {
// expr :: Expr
// expr = Div
// (Div
// (Div (Val 100) (Val 5))
// (Val 2))
// (Div (Val 10) (Val 2))
Expr two = new Val(2);
Expr twenty = new Div(new Val(100), new Val(5));
Expr ten = new Div(twenty, new Val(2));
Expr five = new Div(new Val(10), two);
Expr expr = new Div(ten, five);
// eval :: Expr -> Int
// eval expr = case expr of
ExprVisitor<Integer> eval = new ExprVisitor<Integer>() {
// Val value -> value
public Integer visit(Val val) {
return val.value;
}
// Div left right -> eval left `div` eval right
public Integer visit(Div div) {
return div.left.match(this) / div.right.match(this);
}
};
// main = print (eval expr)
System.out.println(expr.match(eval));
}
}
// data Expr
abstract class Expr {
abstract <T> T match(ExprVisitor<T> visitor);
}
// = Val Int
class Val extends Expr {
public final int value;
public Val(int value) {
this.value = value;
}
<T> T match(ExprVisitor<T> visitor) {
return visitor.visit(this);
}
}
// | Div Expr Expr
class Div extends Expr {
public final Expr left, right;
public Div(Expr left, Expr right) {
this.left = left;
this.right = right;
}
<T> T match(ExprVisitor<T> visitor) {
return visitor.visit(this);
}
}
abstract class ExprVisitor<T> {
abstract T visit(Val val);
abstract T visit(Div div);
}
In the land of functional programming, this is called Böhm–Berarducci encoding—sometimes referred to as Church encoding, although they’re different things. This is a fancy-sounding way of saying “representing data types and pattern matching with functions”. You can of course use this encoding of matching in Haskell:
match
:: (Int -> t) -- visit(Val)
-> (Expr -> Expr -> t) -- visit(Div)
-> Expr
-> t
match val div expr = case expr of
Val x -> val x
Div left right -> div left right
eval :: Expr -> Int
eval = match id (\ left right -> eval left `div` eval right)
Since eval is recursive, you can also write it using the fixed point combinator fix—and then the use of this in the ExprVisitor in the Java version may become more clear: it’s how you make eval recursive!
import Data.Function (fix)
eval :: Expr -> Int
eval = fix $ \ this -> match
(\ value -> value)
(\ left right -> this left `div` this right)
And here’s the other half of the encoding: we can do away with the data type altogether and just use functions:
{-# LANGUAGE RankNTypes #-}
newtype Expr = Expr
{ visit
:: forall a.
(Int -> a) -- Val
-> (a -> a -> a) -- Div
-> a }
valE :: Int -> Expr
valE x = Expr $ \ v _d -> v x
divE :: Expr -> Expr -> Expr
divE left right = Expr $ \ v d
-> d (visit left v d) (visit right v d)
eval :: Expr -> Int
eval expr = visit expr
(\ val -> val)
(\ left right -> left `div` right)
eval (divE
(divE (divE (valE 100) (valE 5)) (valE 2))
(divE (valE 10) (valE 2)))
== 2
And that implementation of eval can of course be written as just this:
eval = visit expr id div
