ADT-like polymorphism in Java (without altering class)

Question

In Haskell I can define following data type: ``` data Tree = Empty | Leaf Int | Node Tree Tree ``` and then write polymorphic function like this: ``` depth :: Tree -> Int depth Empty = 0 depth (Leaf n) = 1 depth (Node l r) = 1 + max (depth l) (depth r) ``` In Java I can emulate algebraic data types with interfaces: ``` interface Tree {} class Empty implements Tree {} class Leaf implements Tree { int n; } class Node implements Tree { Tree l; Tree r; } ``` But if I try to use Haskell-like polymorphism, I get an error: ``` int depth(Empty node) { return 0; } int depth(Leaf node) { return 1; } int depth(Node node) { return 1 + Math.max(depth(node.l), depth(node.r)); // ERROR: Cannot resolve method 'depth(Tree)' } ``` Correct way to overcome this is to put method `depth()` to each class. But what if I don't want to put it there? For example, method `depth()` may be not directly related to `Tree` and adding it to class would break business logic. Or, even worse, `Tree` may be written in 3rd…

Accepted Answer

Try something like this.

Sorry, my Java is very rusty. If, unlike me, you can remember the syntax, you could use Java generics to refine `Object` to `Integer` or whatever class the method you're writing needs. But you can't (can you?) return primitive types, sorry.

```
interface TreeFolder {
    Object onEmpty();
    Object onLeaf (int n);
    Object onNode (Tree l, Tree r);
}

interface Tree {
    Object fold (TreeFolder f);
}

class Empty implements Tree {
    Object fold (TreeFolder f) {
        return f.onEmpty();
    }
}

class Leaf implements Tree {
    private int n;
    Object fold (TreeFolder f) {
        return f.onLeaf (n);
    }
}

class Node implements Tree {
    private Tree l, r;
    Object fold (TreeFolder f) {
        return f.onNode (l, r);
    }
}

// meanwhile, in a class in another package far far away...
Object depth (Tree tree) {
    return tree.fold (new TreeFolder() {
        Object onEmpty() { return new Integer(0); }
        Object onLeaf (int n) { return new Integer(n); }
        Object onNode (Tree l, Tree r) {
            Integer ll = (Integer) l.fold (this);
            Integer rr = (Integer) r.fold (this);
            return new Integer (ll.intValue() + rr.intValue());
        }
    });
}
```

Note that in `depth()` I have to manually recurse (call `fold()`) on the `Tree` parameters. You could instead choose to recurse on them upfront in `Node.fold()` (and change `TreeFolder` accordingly), but then you have to recurse --- you can't choose to recurse only into the left subtree, should you wish to. (In Haskell we don't have to make that trade-off thanks to laziness.)

ADT-like polymorphism in Java (without altering class)

Solution

Problem