What's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?

Question

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

Answer 1

I think that the using a discriminated union together with a mutable record is a good approach. Discriminated unions are essential for pattern matching. An alternative to using mutable record would be to create a union case with mutable reference cells:

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

This may lead to slightly simpler code. For example the insert function would look like this (I didn't try it, but I think it should be correct):

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

However, I don't think this makes the code much more succinct (maybe even slightly less readable). In any case, you could define active pattern to distinguish among the three cases in the insert function using a single match expression. The following is for your original data structure. This is simply an extractor of the elements stored in a record:

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

For more info, see Active Patterns at MSDN. Then, the insert function would look like this:

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) 

[EDIT] Actually, the same thing could be done using patterns for extracting elements of a record, but I think that active patterns may make the code slightly nicer.

Answer 2

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.

If this is an educational exercise then you may well find it easier and more enlightening to implement some of the data structures (such as skip lists) in their purely functional form. Okasaki is a great reference for elegant purely functional data structures and is very enlightening (but of little practical use).

Before I start on something more substantial, is there a better way to do mutable structures like this in F#?

You are working along the right lines. If you want examples, look at this mutable heap implementation written in OCaml by Jean-Christophe Filliatre. There are many other great examples of simple and efficient mutable data structures that use functional programming in their APIs that are written in OCaml.

Should I just use records and not bother with the discriminated union?

In the case of mutable data structures, their parts are often stored contiguously in an array. This is why they are often a lot more efficient than their purely functional counterparts.

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?

No. Do not use F# as if it were a purely functional programming language. The whole point of impure functional languages (and the reason they are far more popular) is that mutation is useful and should not always be avoided. Arrays and hash tables are great data structures. Mutable data structures like the ones you've listed can also be useful.