在F#中进行可变数据结构(例如,跳过列表,splay树)的正确方法是什么？

Question

在F#中实现可变数据结构的好方法是什么？我问的原因是因为我想回去实现我在本学期学习的算法课程中学到的数据结构(跳过列表,splay树,融合树,y-fast尝试,van Emde Boas树等等) .),这是一门纯粹的理论课程,没有任何编码,我想我也可以尝试学习F#,而我正在这样做.我知道我"应该"使用手指树来获取功能语言中的splay树功能,并且我应该做一些懒惰的事情以获得跳过列表功能等,但是我想在尝试之前确定基本知识玩纯粹的功能实现.

有很多的怎么做功能性数据结构在F#的例子,但没有太多关于如何做可变数据结构,所以我一开始就固定了双向链表这里到的东西,允许插入和删除的任何地方.我的计划是将其转换为跳过列表,然后对我想要实现的树结构使用类似的结构(记录的区别联合).在我开始更重要的事情之前,有没有更好的方法在F#中做这样的可变结构？我应该只使用记录而不打扰受歧视的联盟吗？我应该使用课吗？这个问题"甚至没有错"吗？我是否应该在C#中使用可变结构,而不是直到我想将它们与纯功能对应物进行比较？

并且,如果记录的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

但是,我认为这不会使代码更简洁(甚至可能性稍差).在任何情况下,您都可以定义活动模式,以insert使用单个match表达式区分函数中的三种情况.以下是您的原始数据结构.这只是存储在记录中的元素的提取器:

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

有关详细信息,请参阅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) 

[编辑]实际上,使用模式提取记录的元素可以做同样的事情,但我认为活动模式可以使代码稍微好一些.