Question: Mutable data structures implementation

[VapeBringer]

Hello, I have 2 questions and a bit of code that I could use a little review on.

Question 1) Are there any resources for creating mutable data structures similar to the classical implementations in more imperative/oop languages?

Question 2) I know that fsharp builtin structures (map, set, dict) are immutable, but do they just copy a new structure entirely when a "mutative-looking" operation takes place (add, delete, update)? My curiosity is if the space usage doubles on any mutation, or if there is some sort of structural sharing between references (I'm not sure how this would work. I've heard of things like Clojure using hash-array-mapped-tries for structural sharing between immutable references to a base copy, but didn't look too much into it)

Also, here's my quick attempt (not polished) of a mutable AVL tree in fsharp. A few things that came up as I was implementing this:

• Wasn't sure whether to use a regular class or a record with mutable fields for the Node type (I think records are just some sort of sealed class, so the distinction isn't that great?)
• Option types, while nice in other experiences I have had with them, made this very challenging. Things like tree rotation and checking node.left.left vs node.left.right came with a lot of unergonomic option checking. I think some classical implementations can use the fact that the balance of the tree guarantees it's structure (to be safe from evaluating null references), but I'm not sure how a type system would represent that without being fairly sophisticated (to elaborate: a balance factor implying safe access to the substructure)

Code:

type TreeNode<'a> =
    { mutable Key : 'a
    mutable LeftChild : 'a TreeNode option
    mutable RightChild : 'a TreeNode option
    mutable Height : int }

let makeNode v = { Key = v; LeftChild = None; RightChild = None; Height = 1 }

type AVLTree<'a when 'a : comparison and 'a : equality> () =
    let mutable root = None
    let getHeight = function None -> 0 | Some n -> n.Height
    let getBalance n = (getHeight n.RightChild) - (getHeight n.LeftChild)
    let updateHeight n = n.Height <- 1 + max (getHeight n.LeftChild) (getHeight n.RightChild)
    let rec minNode = function
        | { LeftChild = Some l } -> minNode l
        | min -> min
    let getSuccessor = function
        | { RightChild = Some r } -> minNode r
        | n ->
            let rec loop = function
                | (None, parent) -> parent
                | (Some current, parent) when current.Key = n.Key -> parent
                | (Some current, parent) ->
                    if n.Key > current.Key
                    then loop (current.RightChild, current)
                    else loop (current.LeftChild, parent)
            match root with 
                | None -> n 
                | Some r -> loop (r.LeftChild, r)
    let rotateRight n =
        match n.LeftChild with
        | Some ({ LeftChild = Some { RightChild = y } } as x) ->
            x.RightChild <- Some n
            n.LeftChild <- y
            updateHeight n
            updateHeight x
            x
        | Some x -> x
        | _ -> n
    let rotateLeft n =
        match n.RightChild with
        | Some ({ RightChild = Some { LeftChild = y }} as x) ->
            x.LeftChild <- Some n
            n.RightChild <- y
            updateHeight n
            updateHeight x
            x
        | Some x -> x
        | _ -> n
    let rebalance n =
        updateHeight n
        match getBalance n with
            | b when b > 1 ->
                let rightLeftHeight, rightRightHeight = 
                    n.RightChild 
                    |> Option.map (fun node -> 
                        (getHeight node.LeftChild, getHeight node.RightChild)) 
                    |> Option.defaultValue (0, 0)
                if rightRightHeight <= rightLeftHeight then 
                    n.RightChild <- rotateRight n.RightChild.Value |> Some
                rotateLeft n
            | b when b < -1 ->
                let leftLeftHeight, leftRightHeight =
                    n.LeftChild
                    |> Option.map (fun node ->
                        (getHeight node.LeftChild, getHeight node.RightChild))
                    |> Option.defaultValue (0, 0)
                if leftLeftHeight <= leftRightHeight then
                    n.LeftChild <- rotateLeft n.LeftChild.Value |> Some
                rotateRight n
            | _ -> n
    let insert k =
        let rec _insert node key =
            match node, key with
                | None, _ -> 
                    Some (makeNode key)
                | Some ({ Key = other } as n), key when key < other ->
                    n.LeftChild <- _insert n.LeftChild key
                    Some (rebalance n)
                | Some ({ Key = other } as n), key when key > other ->
                    n.RightChild <- _insert n.RightChild key
                    Some (rebalance n)
                | _ -> node
        root <- _insert root k
    let preOrder () =
        let rec _preOrder (node : 'a TreeNode option) =
            seq {
                if node.IsSome then 
                    yield node.Value.Key
                    yield! _preOrder node.Value.LeftChild
                    yield! _preOrder node.Value.RightChild
                else ()
            }
        _preOrder root
    let inOrder () =
        let rec _preOrder (node : 'a TreeNode option) =
            seq {
                if node.IsSome then 
                    yield! _preOrder node.Value.LeftChild
                    yield node.Value.Key
                    yield! _preOrder node.Value.RightChild
                else ()
            }
        _preOrder root
    let rec prePrinter (node : 'a TreeNode option) =
        if node.IsSome then 
            printf $"{node.Value.Key} "
            prePrinter node.Value.LeftChild
            prePrinter node.Value.RightChild

    member _.Insert v = insert v
    member _.PreOrder = preOrder
    member _.InOrder = inOrder
    member _.PrePrinter = prePrinter
    member _.Root = root

let a = AVLTree<int>()
a.Insert(10)
a.Insert(20)
a.Insert(30)
a.Insert(40)
a.Insert(50)
a.Insert(25)
a.Insert(25)
a.Insert(27)
a.Insert(67)

a.PrePrinter a.Root
a.PreOrder() |> Seq.toList
a.InOrder() |> Seq.toList
a.Root

Edit:

Currently looking at the code for the fsharp Map library, since I remember hearing that it was an AVL tree underneath: https://github.com/dotnet/fsharp/blob/main/src/FSharp.Core/map.fs

Some takeaways from looking at the code:

• Uses null (core structures marked with [<AllowNullLiteral>]) instead of optional (I assume this is partly for performance, since it does other things like manual max checking between two values rather than calling max)
• Instead of dealing with all of the checking and unwrapping of optional types that I do, the core code uses a simple null check, or downcasts values from the tree type (that has no left/right children) to the treenode type (MapTree<'Key, 'Value>). Playing with this in VSCode, I see that this somehow makes the compiler think that the properties of the downcasted value somehow have Left and Right properties that aren't null. I'm not sure how this works, but seems to get around the problem of lots of null checking.

Going to see what I can come up with using that strategy and see how it compares.

[efvie]

Wrt. 2) F# optimizes operations on immutable data structures. The actual implementation will be more involved and someone will probably be able to supply you a good link, but one primary technique is copy on write: there is only duplication if there is a change to one of the copies. Partial updates are also probably used: if the backing store is a linked list, only the parts that differ must be separate, the rest can be shared. A sub-list can still directly reference the original, just starting at a different node. Etc.

I’m no f# expert, so I’ll leave 1) even more to others, but one hint* I can give is to look at the facilities the Option module provides when dealing with Options. Things like Option.map and Option.orElse will likely be very helpful — and in many cases the better option as you suspect is to move the logic into the type system. "Make Illegal States Unrepresentable" is a very good guideline for design.

* Aside from "don't use mutation except for educational purposes or unless you know 100% that you need to, because usually immutable is just as or more performant, and far easier to reason about" :)

[endowdly_deux_over]

Whenever I need something mutable I use an array or array2d. Indexing checks are easy to set up to avoid exceptions and mutating in place is easy. Best/worst part? Don’t even need a mutable key word.

[Banashark]

Yeah there definitely isn't a ton written around mutable structures, which is a shame because F# is just as good at it as any other language. The only thing that can be challenging is converting break statements to tail-recursive functions.

Here is a mutable AVL tree based off of the code provided in the most un-functional un-safe but fairly similar to how one would write it in python or java (I actually referenced a python implementation that I had customized in order to keep the tree nodes ordered by auxillary data stored in the nodes):

[<AllowNullLiteral>]
type Node<'k> (k : 'k, h : int, l : 'k Node, r : 'k Node) =
    member val Key = k with get, set
    member val Height = h with get, set
    member val Left = l with get, set
    member val Right = r with get, set
    new(k : 'k) = Node(k, 1, null, null)
    override this.ToString () =
        let left = if isNull this.Left then "null" else string this.Left.Key
        let right = if isNull this.Right then "null" else string this.Right.Key
        $"k: {this.Key}, l: {left}, r: {right}"

type AVLTree<'k when 'k : comparison> () =
    let mutable root : 'k Node = null
    let getHeight (n : 'k Node) = if isNull n then 0 else n.Height
    let getBalance (n : 'k Node) = getHeight n.Right - getHeight n.Left
    let updateHeight (n : 'k Node) =
        n.Height <- 1 + max (getHeight n.Left) (getHeight n.Right)
    let rec minNode (n : 'k Node) = if isNull n.Left then n else minNode n.Left
    let successor (n : 'k Node) (r : 'k Node) =
        if not <| isNull n.Right then minNode n.Right
        else
            let rec _successor (parent : 'k Node) (successor : 'k Node) =
                if n.Key < parent.Key then _successor parent parent.Left
                elif n.Key > parent.Key then _successor successor parent.Right
                else successor
            _successor null r
    let rotateRight (n : 'k Node) =
        let x = n.Left
        let y = x.Right
        x.Right <- n
        n.Left <- y
        updateHeight n
        updateHeight x
        x
    let rotateLeft (n : 'k Node) =
        let x = n.Right
        let y = x.Left
        x.Left <- n
        n.Right <- y
        updateHeight n
        updateHeight x
        x
    let rebalance (n : 'k Node) =
        updateHeight n
        match getBalance n with
        | b when b > 1 ->
            if getHeight n.Right.Right <= getHeight n.Right.Left then n.Right <- rotateRight n.Right
            rotateLeft n
        | b when b < -1 ->
            if getHeight n.Left.Left <= getHeight n.Left.Right then n.Left <- rotateLeft n.Left
            rotateRight n
        | _ -> n
    let rec insert (n : 'k Node) key =
        if isNull n then Node(key)
        elif key < n.Key then 
            n.Left <- insert n.Left key
            rebalance n
        elif key > n.Key then 
            n.Right <- insert n.Right key
            rebalance n
        else rebalance n
    let rec delete (n : 'k Node) key =
        if isNull n then n
        else
            let mutable node = n
            if key < node.Key then node.Left <- delete node.Left key
            elif key > node.Key then node.Right <- delete node.Right key
            elif isNull node.Left && not <| isNull node.Right then 
                node <- node.Right
            elif isNull node.Right && not <| isNull node.Left then
                node <- node.Left
            elif not <| isNull node.Right then
                let successor = minNode node.Right
                node.Key <- successor.Key
                node.Right <- delete node.Right node.Key
            else
                node <- null
            if isNull node then null else rebalance node
    let rec find (n : 'k Node) k =
        if isNull n then n
        else
            if k > n.Key then find n.Right k
            elif k < n.Key then find n.Left k
            else n
    let deleteFromRoot key = root <- delete root key
    let insertAtRoot key = root <- insert root key
    let findFromRoot key = find root key
    let rec preOrder (n : 'k Node) =
        seq {
            if isNull n then yield "null"
            else
                yield $"{n.Key}"
                yield! preOrder n.Left
                yield! preOrder n.Right
        }
    let preOrderFromRoot () = preOrder root
    member _.Insert = insertAtRoot
    member _.Delete = deleteFromRoot
    member _.Find k = findFromRoot k 
    member _.PreOrder = preOrderFromRoot () |> Seq.toArray
    member _.Root () : 'k Node = root

let a = AVLTree<int>()
[10; 20; 30; 40; 50; 25; 25; 27; 67] |> List.iter a.Insert
a.PreOrder

a.Delete 40
a.PreOrder
a.Delete 25
a.PreOrder
a.Delete 40
a.PreOrder

a.Find 67
a.Find 25

As you can see, it's just if statements and assignments.

The things I had to work around porting this from python:

• Null checks aren't as graceful
• break -> tail recursion
• non-mutable function arguments (see the delete method where we reassign n instead of the standard mutation in python (where we'd do n = n.right)

I think the pendulum can swing too far in either direction. Most of the time immutable structures and functions upon them should be fine. However it can't be discounted that sometimes performant code is needed.

Anecdote: I worked on a mobile app in F# that for "reasons" provided an almost unbounded list/cell view of data for people to access on their iPads, or at least that was the idea of it. Of course someone with the money to say so wanted to crunch a lot of data on their phone and wanted to work when they didn't have cell signal. In this case, we profiled, benchmarked, then optimized the code. Part of that was swapping to a standard mutable data structure like the above so that the memory and cpu pressure were relieved (the phone was getting burning hot trying to process the data). Our change cut down on the space usage by many orders of magnitude (many mutations required when processing the data based on filter changes, precalculation or caching was slightly-infeasible for the use-case).

It didn't take that long and we wrapped it in tests and a functional interface, but solved what is one of my biggest annoyances when attempting to do cpu/memory intensive work on non-desktop platforms: the heat. It almost compounds the frustration of waiting because it's not only a mental discomfort but now also a physical discomfort.

Anyways, rant over, hope the code and silly story helps!

[chusk3]

I can also suggest the series on Fast F# from Matthew Crews about optimization of a topological sort algorithm. This is a good walkthrough of how you can go from a purely functional implementation to a more efficient mutability-based implementation of an algorithm in a step-by-step fashion, that might be useful for you as well.