कार्यात्मक कतार प्रकार

Question

मैं एक तरह की कतार डेटा संरचना को कार्यात्मक रूप से प्रस्तुत करना चाहता हूं, लेकिन मुझे वास्तव में कहीं भी नहीं मिला है। मैंने ज़िप्पर में देखा है लेकिन वे सही संरचना नहीं लग रहे हैं।

विशेष रूप से, मैं (गूंज या गूंज की तरह ऑडियो प्रभाव के लिए) देरी लाइनों की एक श्रृंखला का प्रतिनिधित्व करने की कोशिश कर रही है, इसलिए आवश्यक कार्यक्षमता इस प्रकार है:

1. संलग्न सामने
2. दूर करने के लिए डेटा अंतिम आइटम (बस फेंक दिया जा सकता है)

मेरी विशेष उपयोग के लिए, इन दो कार्यों के संयोजन के रूप में इस्तेमाल किया जाएगा के रूप में कतार एक निरंतर आकार रखने के लिए है, लेकिन इस बाधा मौलिक नहीं है। मैं सिर्फ एक सूची का उपयोग कर सकता था, लेकिन मुझे लगता है कि उससे कुछ क्लीनर होना चाहिए। इस प्रकार का प्रतिनिधित्व करने का सबसे अच्छा तरीका क्या है?

मैं एफ # का उपयोग कर रहा हूं, लेकिन किसी भी भाषा का स्वागत है।

Answer 1

कार्यात्मक द्वारा मुझे लगता है कि आप एक अपरिवर्तनीय कतार का मतलब है?

आप एफ # का उपयोग करें और नेट वहाँ उदाहरण के लिए कर रहे हैं:

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

मैं क्रिस द्वारा Purely Functional Data Structures सुझाव है कि आप कैसे एक कार्यात्मक कतार लागू करने के लिए पर पढ़ने के लिए पसंद करते हैं Okasaki।

ओकासाकी कार्यात्मक कतार लागू करने वाले पहले तरीकों में से एक दो List<> का उपयोग कर रहा है, जिसे आप पॉप करते हैं और जिसे आप धक्का देते हैं। जब पॉप सूची खाली होती है तो पुश कतार उलट जाती है और पॉप सूची बन जाती है। मन में

भालू इस एक नहीं बल्कि अक्षम कतार कई मायनों में है लेकिन यह भी नहीं बल्कि सरल है:

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