如何在函数式编程风格中实现这个深度拷贝？

考虑以下结构：如何在函数式编程风格中实现这个深度拷贝？

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，在函数式编程风格。

来源

2012-10-22 象嘉道

在纯FP中，您不会复制，您分享。 –

发表了这个问题后，我认真做了一些调查。我的发现是功能编程不擅长处理流行图算法。

具有纯粹功能性偏好的人必须以不同于正常文献的方式处理图。这是推动家伙产生了如下工作的动机：

与深度优先搜索
图算法懒惰的函数式编程语言
感性的图形和功能图形算法
纯功能数据功能图形算法结构
具有功能风味的图算法

图形算法一直以来都是一种纯粹的功能语言编程挑战。先前的尝试或者倾向于无法读取，或者未能实现标准渐近复杂度度量。

--- John Launchbury。图形算法与功能Flavous。在Advanced Functional Programming中，第一个国际春季学校的高级函数式编程技术 - 教程文本，Johan Jeuring和Erik Meijer（编辑）。 Springer-Verlag，伦敦，英国，308-331。

来源

2012-10-23 16:00:44

如何在函数式编程风格中实现这个深度拷贝？

回答

相关问题