如何在函数式编程风格下实现这种深度复制？

Question

鉴于以下结构：

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)，这样它就不会以functional 风格修改参数。

Answer 1

在贴出这个问题后，我做了一些认真的调查。我的发现是，functional 并不擅长处理流行的图形算法。

纯功能偏好的人必须以与正常的文献不同的方式对待图形。这就是推动男性创作以下作品的动机：

• 基于深度优先搜索的函数图算法
• 图算法懒惰函数编程语言
• 归纳图与函数图算法
• 纯功能数据结构
• 带有功能风味的图算法

图形算法长期以来一直是用纯函数式语言编程的难题。以前的尝试要么是无法读懂，要么是没有达到标准的渐进复杂性度量。

--John Launchbury1995年。带有函数Flavous的图算法。在高级函数式编程，第一国际春季学校高级函数式编程技术-教程文本，约翰·杰灵和埃里克·梅耶尔(Eds.)斯普林格-维拉格，伦敦，英国，308-331。