This post describes the F# implementation of the batched queue from Chris Okasaki’s “Purely functional data structures”.
namespace PurelyFunctionalDataStructures module BatchedQueue = type t<'a> = { Front : list<'a> RBack : list<'a> } let create f r = { Front = f; RBack = r} let empty() = create [] [] let isEmpty q = List.isEmpty q.Front let private checkf = function | [], r -> create (List.rev r) [] | f, r -> create f r let head q = match q.Front with | hd::_ -> hd | _ -> raise Empty let tail q = match q.Front with | hd::tl -> checkf (tl, q.RBack) | _ -> raise Empty let snoc x q = checkf (q.Front, x :: q.RBack) let singleton x = empty() |> snoc x
For a more thourough implementation, see the immutable queue library.
Hmm… let me try that again:
I think it would be more idiomatic to define empty as a generic value of type t< 'a> with the GeneralizableValue attribute applied to it, rather than as a function. That is:
Indeed, with an immutable structure, this totally makes sense. This is what I had done with the immutable queue library.
[...] Ortin’s Purely Functional Data Structures in F#: Batched Queue, Binomal Heap and Red-black [...]