How are Algebaric DataTypes used?

<< Visitor Pattern | Visitor Variations >>

This page explains how to use ADTs, but it doesn't cover exactly what they are or why to use them.

If you have an ADT definition in jADT's syntax for a binary tree

    package com.pogofish.jadt.samples.whathow.data

    IntBinaryTree = 
        Node(int value, IntBinaryTree left, IntBinaryTree right)
      | EmptyTree

Using ant or the shell jADT generates Java code such that with a couple of imports

import com.pogofish.jadt.samples.whathow.data.IntBinaryTree;
import com.pogofish.jadt.samples.whathow.data.IntBinaryTree.*;

import static com.pogofish.jadt.samples.whathow.data.IntBinaryTree.*;

You can create a new Tree with code like

IntBinaryTree tree = _Node(42, _Node(12, _EmptyTree(), _EmptyTree()), _Node(103, _EmptyTree(), _Node(110, _EmptyTree(), _EmptyTree())));

jADT also allows ADTs to be generic. The IntBinaryTree above could be replaced with a more generic version

BinaryTree<T> = 
    Node(T value, BinaryTree<T> left, BinaryTree<T> right) 
  | EmptyTree

With that you can create a String BinaryTree with code like

        BinaryTree<String> empty = BinaryTree.<String>_EmptyTree();

        return _Node("hello", _Node("goodbye", empty, empty), _Node("whatever", empty, _Node("foo", empty, empty)));        

You can also achieve the same thing with 'new BinaryTree.Node<String>("hello"...)' and 'new BinaryTree.EmptyTree<String>()' but that

• constructs new instances of EmptyTree, where _EmptyTree() always reuse the same one.
• requires more typing.
• occasionally creates the less-than-useful (though technically correct) types. E.g. the type of java.util.Colletions.singleton(_EmptyTree) is Set<IntBinaryTree> whereas the type of Collections.singleton(new IntBinaryTree.EmptyTree()) is Set<EmptyTree> which isn't probably very useful.
• requires more type annotation because Java does slightly more type inference with static methods than it does with regular constructors.

Matching on an ADT

In Java you can use "switch" to decide what to do you based on specific values of primitives and Enums. If the primitive happens to be a boolean then you can also use "if" or the ternary operation (x ? y : z). But what about ADTs? How do you decide what to do based on a specific ADT constructor?

Most statically typed functional programming languages have a pattern matching for making decisions based on ADTs. Java doesn't. So with jADT you have a couple of choices, you can use instanceof and casting or preferably you can use the visitor interfaces that jADT generates.

Here's using a MatchBlock style Visitor to find the max of an IntBinaryTree where null indicates an empty tree.

    public Integer max(IntBinaryTree tree)  {
        return tree.match(new IntBinaryTree.MatchBlock<Integer>() {
           @Override
           public Integer _case(Node x) {
              final Integer maxLeft = max(x.left);
              final int l = maxLeft == null ? Integer.MIN_VALUE : maxLeft;

              final Integer maxRight = max(x.right);
              final int r = maxRight == null ? Integer.MIN_VALUE : maxRight;

              return Math.max(Math.max(l, r), x.value);
           }

           @Override
           public Integer _case(EmptyTree x) {
              return null;
           }
        });
     }

Which says that the max of an EmptyTree is null while the max of a Node is the max of the node's value compared with the max of the left tree compared with the max of the right tree.

Languages with pattern matching also generally allow a "don't care" case, a default for when no other case matches. jADT emulates that using a small variation of the visitor pattern.

Given the ADT

TPSReportStatus=
    Pending 
  | Approved(final Manager approver)
  | Denied(final Manager rejector)

You can see if an TPS report was approved by

    public boolean isApproved(TPSReportStatus status) {
        return status.match(new TPSReportStatus.MatchBlockWithDefault<Boolean>() {
            @Override
            public Boolean _case(Approved x) {
                return true;
            }

            @Override
            protected Boolean _default(TPSReportStatus x) {
                return false;
            }
        });
    }

So for Approved the result is true, but for all other statuses (Pending and Denied) the result is false.

In this particular case the same thing could be achieved with instanceof pretty nicely

public boolean isApprovedV2(TPSReportStatus status) {
    return status instanceof TPSReportStatus.Approved;
 }    

A few rules of thumb for when to use instanceof vs a Visitor.

1. If you find yourself casting, stop, use a Visitor
2. If you have a bunch of instanceofs in a row then odds are pretty good you'll make a mistake. Seriously consider using a Visitor.

Besides the Visitor and VisitorWithDefault variations seen on this page, jADT also supports variations that return void.

<< Visitor Pattern | Visitor Variations >>