Functional queue type [duplicate]

Question

I would like to represent a kind of queue data structure functionally, but I haven't really gotten anywhere. I've looked into Zippers but they don't seem to be the right structure.

Specifically, I'm trying to represent a series of delay lines (for audio effects like echo or reverb), so the functionality needed is as follows:

1. Append data to the front
2. Remove the last item (can just be thrown away)

For my particular use, these two operations would be used in conjunction as to keep the queue a constant size, but this constraint is not fundamental. I could just use a list, but I'm thinking there's got to be something cleaner than that. What is the best way to represent this type?

I'm using F#, but any language is welcome.

Answer 1

By functional I assume you mean an immutable queue?

If you use F# and .NET there are for example:

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

If you like to read on how to implement a functional queue I recommend Purely Functional Data Structures by Chris Okasaki.

One of the first ways Okasaki implements a functional queue is using two List<>, one you pop from and one you push to. When the pop list is empty the push queue is reversed and becomes the pop list.

Bear in mind this is in many ways a rather inefficient queue but it's also rather simple:

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