What's a good way to implement mutable data structures in F#? The reason I’m asking is because I want to go back and implement the data structures I learned about in the algorithms class I took this semester (skip lists, splay trees, fusion trees, y-fast tries, van Emde Boas trees, etc.), which was a pure theory course with no coding whatsoever, and I figure I might as well try to learn F# while I’m doing it. I know that I “should” use finger trees to get splay tree functionality in a functional language, and that I should do something with laziness to get skip-list functionality, etc. , but I want to get the basics nailed down before I try playing with purely functional implementations.

There are lots of examples of how to do functional data structures in F#, but there isn’t much on how to do mutable data structures, so I started by fixing up the doubly linked list here into something that allows inserts and deletes anywhere. My plan is to turn this into a skip list, and then use a similar structure (discriminated union of a record) for the tree structures I want to implement. Before I start on something more substantial, is there a better way to do mutable structures like this in F#? Should I just use records and not bother with the discriminated union? Should I use a class instead? Is this question "not even wrong"? Should I be doing the mutable structures in C#, and not dip into F# until I want to compare them to their purely functional counterparts?

And, if a DU of records is what I want, could I have written the code below better or more idiomatically? It seems like there's a lot of redundancy here, but I'm not sure how to get rid of it.

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