Funkcjonalny typ kolejki

Question

Chciałbym reprezentować rodzaj struktury danych kolejki funkcjonalnie, ale tak naprawdę nie dostałem nigdzie. Sprawdziłem Zippers, ale nie wydają się być właściwą strukturą.

szczególności próbuję reprezentują szereg linii opóźniających (dla efektów dźwiękowych takich jak echo i pogłos), więc funkcjonalność potrzebna jest następująca:

1. dołączyć dane do przodu
2. Usuń ostatni element (może być po prostu wyrzucane)

dla mojego konkretnego zastosowania, te dwie operacje byłyby wykorzystywane w połączeniu, aby utrzymać stałą wielkość KOLEJKĄ, ale to ograniczenie nie ma fundamentalne znaczenie. Mogę po prostu użyć listy, ale myślę, że musi być coś czystszego. Jaki jest najlepszy sposób reprezentowania tego typu?

Używam F #, ale każdy język jest mile widziany.

Answer 1

Według funkcjonalności zakładam, że chodzi o niezmienną kolejkę?

Jeśli używasz F # i .NET są na przykład:

• ImmutableQueue<>
• FSharpX.Collections.Queue<>

Jeśli chcesz przeczytać o tym, jak zaimplementować kolejkę funkcjonalne polecam Purely Functional Data Structures przez Chris Okasaki.

Jednym z pierwszych sposobów, w jakie Okasaki implementuje funkcjonalną kolejkę, jest użycie dwóch List<>, z których pop i jednego do którego popchniesz. Kiedy lista jest pusta, kolejka wypychania jest odwrócona i staje się listą pop.

Pamiętaj, to jest pod wieloma względami raczej nieefektywne kolejki ale to też raczej prosty:

type Queue<'T> = 'T list*'T list 

let empty<'T> : Queue<'T> = [], [] 

let isEmpty ((f, r) : Queue<'T>) : bool = 
    match f, r with 
    | [] , [] -> true 
    | _  , _ -> false 

let headAndTail ((f, r) : Queue<'T>) : 'T*Queue<'T> = 
    match f, r with 
    | [] , [] -> failwith "Queue is empty" 
    | v::vs , r -> v, (vs, r) 
    | _  , r -> let v::vs = List.rev r in v, (vs, []) 

let snoc ((f, r) : Queue<'T>) (v : 'T) : Queue<'T> = (f, v::r) 

let fold (f : 'S -> 'T -> 'S) (s : 'S) (q : Queue<'T>) : 'S = 
    let rec loop ss qq = 
    if isEmpty qq then ss 
    else 
     let hh, tt = headAndTail qq 
     loop (f ss hh) tt 
    loop s q 

let ofArray (vs : 'T []) : Queue<'T> = vs |> Array.fold snoc empty 

[<EntryPoint>] 
let main argv = 
    let q = [| 1..20 |] |> ofArray 
    fold (fun _ v -> printfn "%A" v)() q 
    0