如何在函數式編程風格中實現這個深度拷貝？

考慮以下結構：如何在函數式編程風格中實現這個深度拷貝？

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

如何在函數式編程風格中實現這個深度拷貝？

回答

相關問題