What's the right way to do mutable data structures (e.g., skip lists, splay trees) in F#?
- by dan
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
