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

これを克服する正しい方法は、各クラスにメソッドを配置する ことです。しかし、そこに置きたくない場合はどうすればよいですか？たとえば、メソッドはクラスに直接関連していない可能性があり、それをクラスに追加するとビジネス ロジックが壊れます。または、さらに悪いことに、私がアクセスできないサードパーティのライブラリに書かれている可能性があります。この場合、ADT のようなポリモーピズムを実装する最も簡単な方法は何ですか?depth() depth()TreeTree

念のため、現時点では次の構文を使用していますが、これは明らかに好ましくありません。

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()て変更します)が、再帰する必要があります --- 必要に応じて、左側のサブツリーにのみ再帰することを選択することはできません。(Haskell では、遅延のおかげでそのトレードオフを行う必要はありません。)TreeFolder

于 2012-10-05T21:29:12.277 に答える
7

一般的で拡張可能な方法で、これにアプローチできる 1 つの方法の大まかなスケッチを次に示します。すべての場合に直接機能するとは限りませんが、開始するのに役立つ場合があります。

最初に、いくつかの前提条件を示します。

  1. クラスに特定depthのものを追加する必要はありません。Tree
  2. 静的型の利点を失いたくありません。

重要なポイントは、ここで再作成したい Haskell コードはTree型そのものではなく、型のパターン マッチであることを理解することです。そのため、「ツリーでのパターン マッチング」をそれ自体でファースト クラス (ha, ha) エンティティにすることから始めます。Java を何年も使用していないため、C# 風の疑似コードを使用します。

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 が記述されている可能性があります。この場合、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 -> aHaskell で代数データ型を使用すると、ライブラリが公開している場合、外部コード ベースは型のツリー関数を追加できますTree(..) (型自体と 3 つのコンストラクターすべて)。ただし、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 のメソッドをすべてのクラスに 1 回配置する必要があるのは不自然に感じます。メソッドごとに 1 回ツリーをパターン マッチングすることをお勧めします。
于 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 に答える