F # Постоянная переменная размерная структура данных окна

Question

У меня есть описание структуры данных, в которой я нуждаюсь, и я хочу ее реализовать с использованием неизменяемых структур данных. Я пытаюсь определить ... есть ли там существующая структура данных, которая будет поддерживать то, что я пытаюсь сделать здесь, или мне нужно создать ее, - и если мне нужно ее создать, что бы это было хорошо место для запуска (строительные блоки)?

---

У меня есть постоянный поток входящих значений определенного типа. Я хочу добавить их в постоянную/неизменяемую структуру данных, чтобы сохранить их историю, и в каждом добавлении он просмотрит историю и определит, будет ли удален один или несколько самых старых элементов (например, если история> a определенная длина или значение имеет определенное свойство).

Answer 1

Не зная больше о ваших требованиях, я бы сказал, что ваниль Set<'a> выполняет более чем адекватную работу. Я бы предпочел «Установить» над «списком», чтобы у вас всегда был доступ к самым крупным и наименьшим элементам O (lg n), что позволяло вам заказывать ваш набор, вставляя дату/время для эффективного доступа к новейшим и самым старым элементам ,

Кажется очень легко обернуть набор так что его Add/Remove методы вызывать обратные вызовы:

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