0

次の構造があるとします。

class G {
    Node[] nodes;
}
class Node {
    Node neighbour;
}

ディープ コピー操作は、次のように定義できます。

function G copy (G g) {
    G r = new G();
    Map isom = new Map();
    for (Node node in g.nodes) {
        Node c = isom.get(node);
        if (c == null) {
            c = copy(node, isom);
            isom.put(node, c);
        }
        r.nodes.add(c);
    }
    return r;
}
function Node copy(Node n, Map isom) {
    Node r = isom.get(n);
    if (r == null) {
        r = new Node();
        isom.put(n, r);
        r.neighbour = copy(n.neighbour);
    }
    return r;
}

私の質問は、関数型プログラミングスタイルでcopy(Node n, Map isom)引数を変更しないように関数を設計する方法です。isom

4

1 に答える 1

2

この質問を投稿した後、いくつかの調査を真剣に行いました。私が見つけたのは、関数型プログラミングは一般的な グラフ アルゴリズムの処理に適していないということです。

純粋に機能的な好みを持つ人々は、通常の文献とは異なる方法でグラフを扱わなければなりません。それが、次のような作品を生み出すよう男性を後押しする動機です。

  • 深さ優先探索による関数グラフ アルゴリズム
  • グラフ アルゴリズム遅延関数型プログラミング言語
  • 帰納グラフと関数グラフアルゴリズム
  • 純粋に機能的なデータ構造
  • 関数型のグラフ アルゴリズム

グラフ アルゴリズムは、長い間、純粋な関数型言語でプログラミングするのが困難でした。以前の試みは、判読できない傾向があるか、標準の漸近的な複雑さの測定値を達成できませんでした。

---ジョン・ランチベリー。1995. 機能的フレーバーを使用したグラフ アルゴリズム。Advanced Functional Programming では、Advanced Functional Programming Techniques に関する First International Spring School-Tutorial Text、Johan Jeuring および Erik Meijer (Eds.)。Springer-Verlag、ロンドン、英国、308-331。

于 2012-10-23T16:00:44.317 に答える