F＃中可變數據結構（例如，跳過列表，展示樹）的正確方法是什麼？

Question

在F＃中實現可變數據結構的好方法是什麼？我問的原因是因爲我想回去實現我在本學期學習的算法類中學到的數據結構（跳過列表，展開樹，融合樹，y-fast嘗試，van Emde Boas樹等等），這是一門純粹的理論課程，沒有任何編碼，我想我也可以嘗試學習F＃，而我正在做這件事。我知道我「應該」使用手指樹來獲得功能性語言的splay tree功能，並且我應該採取懶惰的方式來獲得跳過列表功能等，但是我想在嘗試之前弄清楚基本知識。玩純粹的功能實現。

有很多關於如何在F＃中完成功能數據結構的例子，但是關於如何做可變數據結構沒有太多的例子，所以我開始將雙鏈表here修改成允許插入和刪除任何地方。我的計劃是把它變成一個跳過列表，然後爲我想實現的樹結構使用類似的結構（有區別的記錄聯合）。在我開始一些更實質的事情之前，有沒有更好的方式在F＃中做這樣的可變結構？我應該只使用記錄，而不用歧視工會嗎？我應該用班級嗎？這個問題「甚至沒有錯」？我是否應該在C＃中做可變結構，並且在我想將它們與純函數進行比較之前不要深​​入F＃中？

而且，如果DU記錄是我想要的，我可以寫更好還是更慣用的代碼？似乎這裏有很多冗餘，但我不知道如何擺脫它。

module DoublyLinkedList = 
    type 'a ll = 
     | None 
     | Node of 'a ll_node 
    and 'a ll_node = { 
     mutable Prev: 'a ll; 
     Element : 'a ; 
     mutable Next: 'a ll; 
    } 

    let insert x l = 
     match l with 
     | None -> Node({ Prev=None; Element=x; Next=None }) 
     | Node(node) -> 
      match node.Prev with 
       | None -> 
        let new_node = { Prev=None; Element=x; Next=Node(node)} 
        node.Prev <- Node(new_node) 
        Node(new_node) 
       | Node(prev_node) -> 
        let new_node = { Prev=node.Prev; Element=x; Next=Node(node)} 
        node.Prev <- Node(new_node) 
        prev_node.Next <- Node(new_node) 
        Node(prev_node) 

    let rec nth n l = 
     match n, l with 
     | _,None -> None 
     | _,Node(node) when n > 0 -> nth (n-1) node.Next 
     | _,Node(node) when n < 0 -> nth (n+1) node.Prev 
     | _,Node(node) -> Node(node) //hopefully only when n = 0 :-) 

    let rec printLinkedList head = 
     match head with 
     | None ->() 
     | Node(x) -> 
      let prev = match x.Prev with 
         | None -> "-" 
         | Node(y) -> y.Element.ToString() 
      let cur = x.Element.ToString() 
      let next = match x.Next with 
         | None -> "-" 
         | Node(y) -> y.Element.ToString() 
      printfn "%s, <- %s -> %s" prev cur next 
      printLinkedList x.Next 

Answer 1

我認爲使用歧視聯合和可變記錄是一種很好的方法。區分的聯合對於模式匹配是必不可少的。使用可變記錄一個辦法是建立一個聯合的情況下與可變參考單元：

// Note: using ´ instead of ' to avoid StackOverflow syntax confusion 
type LinkedList<´T> = 
    | None 
    | Node of (LinkedList<´T> ref) * 'T * (LinkedList<´T> ref) 

這可能導致稍微簡單的代碼。例如，insert功能是這樣的（我沒有嘗試，但我認爲這應該是正確的）：

let insert x l = 
    match l with 
    | None -> Node(ref None, x, ref None) 
    | Node(prev, v, next) as node -> 
     match !prev with 
     | None -> 
     prev := Node(ref None, x, ref node) 
     !prev 
     | Node(_, _, prevNextRef) -> 
     prevNextRef := Node(ref (!node.Prev), x, ref node) 
     prev := !prevNextRef 
     !prevNextRef 

不過，我不認爲這使得代碼更簡潔（甚至可讀性稍差）。在任何情況下，您都可以使用單個match表達式定義活動模式以區分insert函數中的三種情況。以下是您的原始數據結構。這簡直是​​存儲在一個記錄元素的提取：

let (|NodeInfo|) node = (node.Prev, node.Element, node.Next) 

欲瞭解更多信息，請參閱Active Patterns at MSDN。然後，insert功能應該是這樣的：

let insert x l = 
    match l with 
    | None -> Node({ Prev=None; Element=x; Next=None }) 
    | Node(NodeInfo(None, _, _) as node) -> 
     let new_node = { Prev=None; Element=x; Next=Node(node)} 
     node.Prev <- Node(new_node) 
     Node(new_node) 
    | Node(NodeInfo(Node(prev_node), _, _) as node) ->    
     let new_node = { Prev=node.Prev; Element=x; Next=Node(node)} 
     node.Prev <- Node(new_node) 
     prev_node.Next <- Node(new_node) 
     Node(prev_node) 

[編輯]其實，同樣的事情可以使用模式進行抽取一個記錄的要素做，但我認爲，積極的模式可能會使代碼略微更好。

Answer 2

我問的原因是因爲我想返回去實現我在算法類中學到的數據結構，我花了這個學期（跳過列表，展開樹，融合樹，y-fast嘗試， van Emde Boas樹等），這是一門純粹的理論課程，沒有任何編碼，我想我也可以嘗試學習F＃，而我正在做這件事。

如果這是一項教育性練習，那麼您可能會發現，以其純功能形式實現一些數據結構（如跳過列表）會更容易，更有啓發性。岡崎是優雅的純功能數據結構的一個很好的參考，非常有啓發性（但實際使用很少）。

在我開始一些更實質的事情之前，有沒有更好的方式在F＃中做這樣的可變結構？

您正在沿着正確的路線工作。如果您想要示例，請看Jean-Christophe Filliatre在OCaml中編寫的mutable heap implementation。在OCaml中編寫的API中使用函數式編程的簡單而高效的可變數據結構還有很多其他很好的例子。

我是否應該只使用記錄而不用歧視的工會？

在可變數據結構的情況下，它們的部分通常連續存儲在一個數組中。這就是爲什麼他們往往比純粹功能的同行更有效率。

我應該在做C＃中的可變結構，而不是深入到F＃，直到我想將它們與它們的純函數對應對比？

編號不要使用F＃，就好像它是純粹的函數式編程語言。不純的功能語言（以及它們更受歡迎的原因）的要點是突變是有用的，不應總是避免。數組和散列表是偉大的數據結構。像你列出的那些可變的數據結構也是有用的。