Функциональная очередь типа

Question

Я хотел бы представлять структуру данных очереди как функционально, но я нигде не получил. Я посмотрел на Молнии, но они, похоже, не являются правильной структурой.

В частности, я пытаюсь представить ряд линий задержки (для звуковых эффектов, таких как эхо или реверберация), так что функциональные возможности, необходимые следующим образом:

1. добавить данные в передней
2. Вытащите последний элемент (можно просто выбросить)

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

Я использую F #, но любой язык приветствуется.

Answer 1

По функциональности я предполагаю, что вы имеете в виду непреложную очередь?

Если вы используете F # и .NET есть, например:

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

Если вы хотите прочитать о том, как реализовать функциональную очередь я рекомендую Purely Functional Data Structures Крисом Okasaki.

Один из первых способов, которым Окасаки реализует функциональную очередь, состоит в использовании двух List<>, по одному из которых вы нажимаете и нажимаете. Когда список постов пуст, то очередь push меняется на противоположную и становится списком pop.

Имейте в виду, что это во многом довольно неэффективный очереди, но это также довольно просто:

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