İşlevsel sıra tipi

Question

İşlevsel olarak bir sıra veri yapısını temsil etmek istiyorum, ancak gerçekten hiçbir yere ulaşmadım. Fermuarlara baktım ama doğru yapı gibi görünmüyorlar.

Özellikle, (yankı ya da yankı gibi ses efektleri için) gecikme hatlarının bir dizi temsil etmek çalışıyorum, bu yüzden aşağıdaki gibi gerekli işlevselliği: Ön

Kaldırmak

1. ekleme verilerini son madde kuyruğunu sabit boyuta tutmak için bu iki işlem birlikte kullanılabilir olacağını, benim özel kullanım için

(sadece atılır olabilir), ancak bu kısıt temel değildir. Sadece bir liste kullanabilirim ama sanırım bundan daha temiz bir şey olmalı. Bu türü temsil etmenin en iyi yolu nedir?

F # kullanıyorum, ancak herhangi bir dile hoş geldiniz.

Answer 1

İşlevsel olarak, değişmez bir sırayı mı kastediyorsunuz?

F # kullanmak ve .NET örneğin varsa: Bir fonksiyonel kuyruğunu nasıl uygulanacağı konusunda okumayı seviyorsanız

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

Chris tarafından Purely Functional Data Structures tavsiye Okasaki.

Okasaki'nin işlevsel bir sıra uyguladığı ilk yollardan biri, sizden bir diğerine ittiğiniz iki List<> kullanıyor. Pop listesi boş olduğunda, itme sırası tersine çevrilir ve pop listesi haline gelir. (Http://hackage.haskell.org/package [ `Data.Sequence`]: akılda

Ayı bu birçok yönden oldukça verimsiz kuyruk ama aynı zamanda oldukça basit:

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