F# 不可变的可变大小窗口数据结构

Question

下面是我需要的数据结构的描述，我想使用不可变的数据结构来实现它。我试图确定......是否有一个现有的数据结构可以支持我在这里尝试做的事情，或者我是否需要创建一个数据结构 - 如果我需要创建它，什么会是一个好的从哪里开始（构建块）？

---

我有稳定的某种类型的传入值流。我想将它们添加到持久/不可变的数据结构中以保存它们的历史记录，并且在每次添加时，它将查看历史记录并确定是否将删除一个或多个最旧的项目（例如，如果历史记录> >）。一定的长度或值具有一定的属性）。

Answer 1

在不了解更多关于您的要求的情况下，我只想说普通 Set<'a> 的工作绰绰有余。我更喜欢“集合”而不是“列表”，这样您始终可以 O(lg n) 访问最大和最小的项目，从而允许您通过插入日期/时间来订购集合，以便有效地访问最新和最旧的项目。

似乎很容易包装一个集合，以便其添加/删除方法调用您的回调：

type AwesomeSet(internalSet : Set<'a>, insertCallback : 'a -> unit, removeCallback : 'a -> unit) =
    member this.Add(x) =
        insertCallback(x)
        AwesomeSet(internalSet.Add x, insertCallback, removeCallback)

    member this.Remove(x) =
        removeCallback(x)
        AwesomeSet(internalSet.Remove x, insertCallback, removeCallback)

    member this.Count = internalSet.Count
    member this.Min = internalSet.MinimumElement
    member this.Max = internalSet.MaximumElement

Answer 2

感谢朱丽叶的善意信息，我已经实现了我需要的内容，并将其放在这里，以防其他人发现它有用。

let rec removeLast (s : Set<'a>, num : int) : Set<'a> = 
    match num with
    | 0 -> s
    | _ -> removeLast(s.Remove(s.MinimumElement), num-1)


type History<'a when 'a : comparison>(underlying : Set<'a>, removal : History<'a> -> int) =
    member this.Add(x) =
        History(removeLast(underlying, removal(this)).Add x, removal)

    member this.Count = underlying.Count
    member this.Min = underlying.MinimumElement
    member this.Max = underlying.MaximumElement
    member this.Under = underlying

let maxHist = 2
let maxCountRemover (h : History<int>) =
    if h.Count >= maxHist
    then h.Count - maxHist + 1
    else 0


let testHistory =
    let s = History(Set.empty, r)
    let s = s.Add(1);
    printfn "%i: %i - %i" s.Count s.Min s.Max
    let s = s.Add(2);
    printfn "%i: %i - %i" s.Count s.Min s.Max
    let s = s.Add(3);
    printfn "%i: %i - %i" s.Count s.Min s.Max
    let s = s.Add(4);
    printfn "%i: %i - %i" s.Count s.Min s.Max
    let s = s.Add(5);
    printfn "%i: %i - %i" s.Count s.Min s.Max
    printfn "%A" s.Under