Priority list implementation in F#

SimplePriorityList.fsx

// Exercise from https://blog.ploeh.dk/2024/06/12/simpler-encapsulation-with-immutability/
// Invariants to maintain:
// - budget > 0
// - dividers has at least 2 elements, is sorted, has first element = 0 and last element = budget.
type PriorityList = { budget: int; dividers: int list }

let create (numItems: int) (budget: int) : PriorityList =
    { budget = budget
      dividers = List.init numItems (fun _ -> 0) @ [ budget ] }

// We can switch from the space of dividers to the space of priorities and vice-versa.
// Each may be useful to check different invariants.
let _toPriorities (dividers: int list) : int list =
    List.tail dividers
    |> List.zip (List.take (dividers.Length - 1) dividers)
    |> List.map (fun (pLower, pUpper) -> pUpper - pLower)

let _toDividers (priorities: int list) : int list =
    priorities |> List.fold (fun acc p -> acc @ [ p + List.last acc ]) [ 0 ]

let getAll (plist: PriorityList) : int list = _toPriorities plist.dividers

let get (itemIdx: int) (plist: PriorityList) : int option =
    Option.map2 (fun x y -> x - y) (List.tryItem (itemIdx + 1) plist.dividers) (List.tryItem itemIdx plist.dividers)

let set (itemIdx: int) (priority: int) (plist: PriorityList) : PriorityList =
    // Set the given item to [priority]. The needed priority is taken from the other items in reverse order.
    let reducedPriorities, _ =
        List.mapFoldBack
            (fun p debt ->
                if debt = 0 then p, 0
                else if p >= debt then p - debt, 0
                else 0, debt - p)
            (_toPriorities plist.dividers)
            priority

    let newPriorities =
        List.mapi (fun i p -> if i = itemIdx then p + priority else p) reducedPriorities

    { plist with
        dividers = _toDividers newPriorities }

// Adds a new item to the end of the priority list.
let addItem (plist: PriorityList) : PriorityList =
    { plist with
        dividers = plist.dividers @ [ plist.budget ] }

// Removes the last item from the priority list, allocating its priority to the preceding item.
let removeItem (itemIdx: int) (plist: PriorityList) : PriorityList =
    if (plist.dividers.Length <= 2) then
        plist // Cannot remove if there is only one item left
    else
        let oldPriorities = plist.dividers |> _toPriorities
        let removed = List.item itemIdx oldPriorities

        let newPriorities =
            oldPriorities
            |> List.removeAt itemIdx
            |> List.mapi (fun i p ->
                let lastIdx = plist.dividers.Length - 3
                if (i = lastIdx && i <> 0) then p + removed else p)

        { plist with
            dividers = _toDividers newPriorities }

let toString (plist: PriorityList) =
    sprintf "Priorities: %A (total budget %i)" (_toPriorities plist.dividers) plist.budget

// Sample script
let budget = 100
let plist = create 4 budget

printfn "%s" (toString plist)

let finalList =
    plist
    |> set 0 25
    |> addItem
    |> set 1 0
    |> set 2 25
    |> set 3 0
    |> addItem
    |> set 4 20
    |> set 5 30
    |> set 1 10
    |> set 1 80

printfn "%s" (toString finalList)