10

在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可能是在我无法访问的 3rd 方库中编写的。在这种情况下，实现类似 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());
}
4

6 回答 6

10

尝试这样的事情。

抱歉，我的 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相应地进行更改），但是您必须递归 --- 如果您愿意，您不能选择仅递归到左子树。（在 Haskell 中，由于懒惰，我们不必进行这种权衡。）

于 2012-10-05T21:29:12.277 回答
7

这是您可以以一种通用且可扩展的方式处理此问题的一种方法的粗略草图。它不会在所有情况下都直接起作用，但可能会帮助您入门。

首先，一些初始假设：

  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
                             }

...可以很容易地看出它直接对应于 case 表达式：

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

顺便说一句，这种具体化的模式匹配在 OOP 圈子中被称为“访问者模式”。

于 2012-10-05T21:33:39.950 回答
7

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

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

于 2012-10-05T21:37:37.467 回答
5

@stemm 是正确的，访问者模式非常适合这个问题。但是，我还建议您查看众所周知的访问者模式的修改版本。一位博主发明了这种教堂编码模式。这种模式比访问者模式更密集，并且具有更多的功能风格。

于 2012-10-06T16:53:19.387 回答
2

编辑：这是您不想要的答案（放在depth()界面中Tree），但我认为无论如何它都值得全面分析。

更广泛地说，这是使用 classes 实现sum 类型的问题。在面向对象的语言中有一种非常常见的求和类型的方法。即解释器模式。

interface Tree { int depth(); }

class Empty implements Tree { int depth(){ return 0; }

class Leaf implements Tree {
  int n;
  int depth(){ return 1; }
}

class Node implements Tree {
  Tree l; Tree r;
  int depth(){ return max(depth(l), depth(r)); }
}

让我们将其与 haskell 方法进行比较！很明显，类的作者可以有任意多种类型（Empty, Leaf, Node）和方法（depth(), numLeafs()）。但是，想要扩展这个树库的外部代码呢？

:: Tree -> a在 haskell 中使用代数数据类型，如果库公开Tree(..) （类型本身和所有三个构造函数），外部代码库可以添加类型的树函数。但是，不能向 中添加新的构造函数Tree，如下所示：

-- Code far far away can't do this in haskell
data Tree = ...
          | ...
          | Node3 Tree Tree Tree

但是在java中使用解释器模式时，情况正好相反。不能向Tree接口添加新方法，但可以像这样添加新的构造函数：

-- Code far far away *can* do this in java
class Node3 implements Tree {
  Tree l; Tree mid; Tree r;
  int depth(){ ... }
}

总之，这种设计模式在以下情况下非常有效：

  • 其他人想在代数数据结构中添加项。
  • 您需要完整的类型安全性

但这有点不令人满意，因为：

  • 其他人不能添加减速器功能，如numNodes()
  • Trees 上的方法必须在每个类中放置一次，这感觉有些做作。我们更喜欢每个方法对树进行一次模式匹配，而不是我们以一种转置的方式进行。
于 2012-10-06T16:44:49.387 回答
1

我还没有找到任何令人愉快的解决方案。

我希望这可以帮助你。

interface Tree {
}

class Empty implements Tree {
}

class Leaf implements Tree {
    int n;
}

class Node implements Tree {
    Tree l;
    Tree r;
}

class Test{

    public static void main (String args[]){

        Test p = new Test();
        Empty e = new Empty();      
        System.out.println(p.depth(e));
        Leaf t = new Leaf();
        System.out.println(p.depth(t));     
        Node n = new Node();
        n.l = t;
        n.r = e;
        System.out.println(p.depth(n));
    }

    int depth(Tree tree) {
        if(tree instanceof Leaf){
            return 1;
        }
        return 0;    
    }

    int depth(Node node) {
        return 1 + Math.max(depth(node.l), depth(node.r));  
    }   

}
    }

祝你好运！

于 2012-10-05T21:32:20.937 回答