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 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, and 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. 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?

Also, VS warns me about 'nth', because I pattern match on 0, and then have a when clause that looks for < 0 and > 0. What's a better way to write that function?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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
        | 0,_ -> l
        | _,None -> None
        | _,Node(node) when n > 0 -> nth (n-1) node.Next 
        | _,Node(node) when n < 0 -> nth (n+1) node.Prev 


    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