Java中的ADT类多态(不改变类)

Question

在Haskell中,我可以定义以下数据类型:

data Tree = Empty
      | Leaf Int
      | Node Tree Tree

然后写这样的多态函数:

depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

在Java中,我可以使用接口模拟代数数据类型:

interface Tree {}
class Empty implements Tree {}
class Leaf implements Tree { int n; }
class Node implements Tree { Tree l; Tree r; }

但是,如果我尝试使用类似Haskell的多态,我会收到一个错误:

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)'
}

克服这个问题的正确方法是将方法放在 depth() 每个班级.但是,如果我不想把它放在那里怎么办？例如,方法depth()可能不直接相关,Tree并将其添加到类将破坏业务逻辑.或者,更糟糕的是,Tree可能会写在我无法访问的第三方库中.在这种情况下,实现类似ADT的多态性的最简单方法是什么？

为了以防万一,目前我正在使用以下语法,这显然是不受欢迎的:

int depth(Tree tree) {
    if (tree instanceof Empty) depth((Empty)tree)
    if (tree instanceof Leaf) depth((Leaf)tree);
    if (tree instanceof Node) depth((Node)tree); 
    else throw new RuntimeException("Don't know how to find depth of " + tree.getClass());
}

Answer 1

尝试这样的事情.

对不起,我的Java非常生疏.如果,不像我,你能记住的语法,你可以使用Java泛型细化Object到Integer或任何类你写需求的方法.但你不能(你能吗？)返回原始类型,抱歉.

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());
        }
    });
}

请注意,depth()我必须手动递归(调用fold())Tree参数.你可以选择预先递归它们Node.fold()(并相应地改变TreeFolder),但是你必须递归 - 如果你愿意,你不能选择只递归到左子树.(在哈斯克尔,由于懒惰,我们不必做出这种权衡.)

Answer 2

这是一个粗略的草图,你可以通过一般和可扩展的方式来解决这个问题.它不会直接在所有情况下都有效,但可能会帮助您入门.

首先,一些开始的假设:

1. 我们不希望任何特定的内容depth添加到Tree类中.
2. 我们不想失去静态类型的好处.

关键是要意识到你想在这里重新创建的Haskell代码不是Tree类型本身,而是模式匹配.因此,我们首先将"树上的模式匹配"本身作为第一类(ha,ha)实体.使用C#-ish伪代码,因为我多年没有使用过Java:

interface MatchTree<R> 
{
    R matchEmpty(Empty empty);
    R matchLeaf(Leaf leaf);
    R matchNode(Node node);
}

要使用此已确定的模式匹配,我们需要一个适当的方法Tree:

interface Tree
{
    R patternMatch<R>(MatchTree<R> patterns);
}

Tree然后,每个单独的子类型可以通过调用适当的MatchTree方法并将自身作为参数来实现该函数.

等效的Haskell将是这样的:

data MatchTree r = MatchTree { matchEmpty :: r
                             , matchLeaf :: Int -> r
                             , matchNode :: Tree -> Tree -> r
                             }

...可以很容易地看到与案例表达直接对应:

match tree z fl fn = case tree of
                       Empty -> z
                       Leaf x -> fl i
                       Node lt rt -> fn lt rt

这种风格的模式匹配在OOP圈子中被称为"访客模式",顺便说一句.

Answer 3

例如,方法depth()可能与Tree没有直接关系,将它添加到class会破坏业务逻辑.或者,更糟糕的是,Tree可能写在我无法访问的第三方库中.在这种情况下,实现类似ADT的多态性的最简单方法是什么？

在这种情况下 - 我建议你使用设计模式访问者.它允许您分离数据表示和处理逻辑,甚至更多 - 它允许您实现不同的处理策略.

Answer 4

@stemm是正确的，访问者模式非常适合此问题。但是，我也建议您查看著名的访问者模式的修改版本。一个博主发明了这种教堂编码模式。与访问者模式相比，此模式更密集且具有更多的功能样式。