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. 具有功能特征的图算法。在高级函数式编程中，First International Spring School on Advanced Functional Programming Techniques-Tutorial Text，Johan Jeuring 和 Erik Meijer (Eds.)。Springer-Verlag，伦敦，英国，308-331。

于 2012-10-23T16:00:44.317 回答