10 Dec'09
Batched queue

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.

3 Responses to “Batched queue”

  1. Keith says:

    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:

    [<GeneralizableValue>]
    let empty<'a> : t<'a> = create [] []
    
  2. julien says:

    Indeed, with an immutable structure, this totally makes sense. This is what I had done with the immutable queue library.

  3. [...] Ortin’s Purely Functional Data Structures in F#: Batched Queue, Binomal Heap and Red-black [...]