An immutable queue library in F#. The queue is divided into two lists : one for dequeueing, and one for enqueueing. All operations are based on the List module.

There are a few exceptions however : operations involving arithmetic (such as List.sum) are not included.

Source

// Adapted from F# ListEnumerator from fslib/prim-types.fs

type private QueueEnumerator<'a>(enqueued : 'a list, toDequeue :'a list) =
  static let notStarted() =
    raise (new System.InvalidOperationException("Enumeration has not started. Call MoveNext."))

  static let alreadyFinished() =
    raise (new System.InvalidOperationException("Enumeration already finished."))

  static let nonempty x = not <| List.isEmpty x 

  let mutable backData = enqueued
  let mutable frontData = toDequeue
  let moveBackToFront() =
    match frontData, backData with
    | [], hd::tl -> frontData <- List.rev backData
    | _ -> ()

  let mutable started = false

  member x.GetCurrent() =
    if started then
      moveBackToFront()
      match frontData with
      | hd :: tl -> hd
      | [] -> alreadyFinished()
    else
      notStarted()

  interface System.Collections.Generic.IEnumerator<'a> with
    member x.Current = x.GetCurrent()

  interface System.Collections.IEnumerator with
    member x.MoveNext() =
      moveBackToFront()
      if started then
        match frontData with
        | hd::tl ->
            frontData <- tl
            nonempty frontData
        | [] -> false
      else
        started <- true
        nonempty frontData

    member x.Current = box (x.GetCurrent())

    member x.Reset() =
      started <- false
      backData <- enqueued
      frontData <- toDequeue

  interface System.IDisposable with
    member x.Dispose() = ()  

type Queue<'a> =
  { enqueued : 'a list
    toDequeue : 'a list
  }
  interface System.Collections.Generic.IEnumerable<'a> with
    member x.GetEnumerator() =
      (new QueueEnumerator<'a>(x.enqueued, x.toDequeue) :> System.Collections.Generic.IEnumerator<'a>)

  interface System.Collections.IEnumerable with
    member x.GetEnumerator() =
      (new QueueEnumerator<'a>(x.enqueued, x.toDequeue) :> System.Collections.IEnumerator)  

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Queue =

  type t<'a> = Queue<'a>

  let unsafe_create enqueued toDequeue =
    { enqueued = enqueued
      toDequeue = toDequeue
    }  

  let toList xs = xs.toDequeue @ List.rev xs.enqueued

  let ofList xs = unsafe_create [] xs

  [<GeneralizableValueAttribute ()>]
  let empty<'a> : Queue<'a> = unsafe_create [] []

  let rec peek q =
    match q.enqueued, q.toDequeue with
    | _, hd::tl -> hd
    | hd::tl as e, [] -> e |> List.rev |> List.head
    | _ -> invalidArg "q" "peek : empty queue"

  let rec tryPeek q =
    match q.enqueued, q.toDequeue with
    | _, hd::tl -> Some hd
    | hd::tl as e, [] -> e |> List.rev |> ofList |> tryPeek
    | _ -> None

  let enqueue x q = {q with enqueued = x :: q.enqueued}

  let rec dequeue q =
    match q.enqueued, q.toDequeue with
    | _, hd::tl -> hd, {q with toDequeue = tl}
    | hd::tl as e, [] -> e |> List.rev |> ofList |> dequeue
    | _ -> invalidArg "q" "dequeue : empty queue"

  let rec tryDequeue q =
    match q.enqueued, q.toDequeue with
    | _, hd::tl -> Some (hd, {q with toDequeue = tl})
    | hd::tl as e, [] -> e |> List.rev |> ofList |> tryDequeue
    | _ -> None

  let append xs xs' = List.append (toList xs) (toList xs') |> ofList
  let choose f xs =
    unsafe_create (List.choose f xs.enqueued) (List.choose f xs.toDequeue)
  let collect f xs =
    unsafe_create (List.collect f xs.enqueued) (List.collect f xs.toDequeue)
  let concat xss = unsafe_create [] [for xs in xss do yield! toList xs]
  let exists p xs =
    List.exists p xs.enqueued || List.exists p xs.toDequeue
  let exists2 p xs xs' = List.exists2 p (toList xs) (toList xs')
  let filter p xs =
    unsafe_create (List.filter p xs.enqueued) (List.filter p xs.toDequeue)
  let find p xs =
    match List.tryFind p xs.toDequeue with
    | None -> List.find p (List.rev xs.enqueued)
    | Some x -> x
  let findAll p xs = filter p xs
  let findIndex p xs =
    match List.tryFindIndex p xs.toDequeue with
    | None -> List.findIndex p (List.rev xs.enqueued)
    | Some x -> x
  let fold f v xs = xs |> toList |> List.fold f v
  let fold2 f v xs xs' = List.fold2 f v (toList xs) (toList xs')
  let foldBack f xs v = List.foldBack f (toList xs) v
  let foldBack2 f xs xs' v = List.foldBack2 f (toList xs) (toList xs') v
  let forAll p xs =
    List.forall p xs.enqueued && List.forall p xs.toDequeue
  let forAll2 p xs xs' =
    List.forall2 p (toList xs) (toList xs')
  let head xs = peek xs
  let init n f = List.init n f |> ofList
  let isEmpty q = List.isEmpty q.enqueued && List.isEmpty q.toDequeue
  let iter f xs =
    List.iter f xs.toDequeue
    xs.enqueued |> List.rev |> List.iter f
  let iter2 f xs xs' = List.iter2 f (toList xs) (toList xs')
  let iteri f xs =
    List.iteri f xs.toDequeue
    xs.enqueued |> List.rev |> List.iteri f
  let iteri2 f xs xs' = List.iteri2 f (toList xs) (toList xs')
  let length xs =
    List.length xs.enqueued + List.length xs.toDequeue
  let map f xs =
    unsafe_create (List.map f xs.enqueued) (List.map f xs.toDequeue)
  let map2 f xs xs' =
    List.map2 f (toList xs) (toList xs') |> ofList
  let map3 f xs xs' xs'' =
    List.map3 f (toList xs) (toList xs') (toList xs'') |> ofList
  let mapi f xs =
    unsafe_create (List.mapi f xs.enqueued) (List.mapi f xs.toDequeue)
  let mapi2 f xs xs' =
    List.mapi2 f (toList xs) (toList xs') |> ofList
  let nonempty xs = not <| isEmpty xs
  let nth xs pos =
    if pos > xs.toDequeue.Length then
      List.nth (List.rev xs.enqueued) (pos - xs.toDequeue.Length)
    else
      List.nth xs.toDequeue pos
  let fromArray xs = xs |> List.ofArray  |> ofList
  let toArray xs = xs |> toList |> List.toArray
  let fromSeq xs = xs |> List.ofSeq |> ofList
  let toSeq xs = xs |> toList |> List.toSeq
  let min xs = List.min (toList xs)
  let minBy f xs = List.minBy f (toList xs)
  let max xs = List.max (toList xs)
  let maxBy f xs = List.maxBy f (toList xs)
  let partition p xs =
    let enqueuedA, enqueuedB = List.partition p xs.enqueued
    let toDequeueA, toDequeueB = List.partition p xs.toDequeue
    unsafe_create enqueuedA toDequeueA, unsafe_create enqueuedB toDequeueB
  let permute f xs =
    xs |> toList |> List.permute f |> ofList
  let pick p xs =
    match List.tryPick p xs.toDequeue with
    | None -> List.pick p (List.rev xs.enqueued)
    | Some res -> res
  let reduce f xs = xs |> toList |> List.reduce f
  let reduceBack f xs = xs |> toList |> List.reduceBack f
  let replicate n x = List.replicate n x |> ofList
  let rev xs =
    unsafe_create (List.rev xs.toDequeue)  (List.rev xs.enqueued)
  let scan f v xs = xs |> toList |> List.scan f v |> ofList
  let scanBack f xs v = List.scanBack f (toList xs) v |> ofList
  let sort xs = List.sort (toList xs) |> ofList
  let sortBy f xs = List.sortBy f (toList xs) |> ofList
  let sortWith f xs = List.sortWith f (toList xs) |> ofList
  let tail xs  =
    let hd, tl = dequeue xs
    tl
  let tryFind p xs =
    match List.tryFind p xs.toDequeue with
    | None -> List.tryFind p (List.rev xs.enqueued)
    | Some _ as res -> res
  let tryFindIndex p xs =
    match List.tryFindIndex p xs.toDequeue with
    | None -> List.tryFindIndex p (List.rev xs.enqueued)
    | Some _ as res -> res
  let tryPick p xs =
    match List.tryPick p xs.toDequeue with
    | None -> List.tryPick p (List.rev xs.enqueued)
    | Some _ as res -> res

Signature

type Queue<'a> =
  { enqueued : 'a list
    toDequeue : 'a list
  }
    interface System.Collections.IEnumerable
    interface System.Collections.Generic.IEnumerable<'a>

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Queue =
  type t<'a> = Queue<'a>

  val toList : t<'a> -> 'a list
  val ofList : 'a list -> t<'a>
  val empty<'a> : t<'a>
  val peek : t<'a> -> 'a
  val tryPeek : t<'a> -> 'a option
  val enqueue : 'a -> t<'a> -> t<'a>
  val dequeue : t<'a> -> 'a * t<'a>
  val tryDequeue : t<'a> -> ('a * t<'a>) option

  val append : t<'a> -> t<'a> -> t<'a>
  val choose : ('a -> 'b option) -> t<'a> -> t<'b>
  val collect : ('a -> 'b list) -> t<'a> -> t<'b>
  val concat : seq<t<'a>> -> t<'a>
  val exists : ('a -> bool) -> t<'a> -> bool
  val exists2 : ('a -> 'b -> bool) -> t<'a> -> t<'b> -> bool
  val filter : ('a -> bool) -> t<'a> -> t<'a>
  val find : ('a -> bool) -> t<'a> -> 'a
  val findAll : ('a -> bool) -> t<'a> -> t<'a>
  val findIndex : ('a -> bool) -> t<'a> -> int
  val fold : ('a -> 'b -> 'a) -> 'a -> t<'b> -> 'a
  val fold2 : ('a -> 'b -> 'c -> 'a) -> 'a -> t<'b> -> t<'c> -> 'a
  val foldBack : ('a -> 'b -> 'b) -> t<'a> -> 'b -> 'b
  val foldBack2 : ('a -> 'b -> 'c -> 'c) -> t<'a> -> t<'b> -> 'c -> 'c
  val forAll : ('a -> bool) -> t<'a> -> bool
  val forAll2 : ('a -> 'b -> bool) -> t<'a> -> t<'b> -> bool
  val head : t<'a> -> 'a
  val init : int -> (int -> 'a) -> t<'a>
  val isEmpty : t<'a> -> bool
  val iter : ('a -> unit) -> t<'a> -> unit
  val iter2 : ('a -> 'b -> unit) -> t<'a> -> t<'b> -> unit
  val iteri : (int -> 'a -> unit) -> t<'a> -> unit
  val iteri2 : (int -> 'a -> 'b -> unit) -> t<'a> -> t<'b> -> unit
  val length : t<'a> -> int
  val map : ('a -> 'b) -> t<'a> -> t<'b>
  val map2 : ('a -> 'b -> 'c) -> t<'a> -> t<'b> -> t<'c>
  val map3 : ('a -> 'b -> 'c -> 'd) -> t<'a> -> t<'b> -> t<'c> -> t<'d>
  val mapi : (int -> 'a -> 'b) -> t<'a> -> t<'b>
  val mapi2 : (int -> 'a -> 'b -> 'c) -> t<'a> -> t<'b> -> t<'c>
  val min : t<'a> -> 'a when 'a:comparison
  val minBy : ('a -> 'b) -> t<'a> -> 'a when 'b:comparison
  val max : t<'a> -> 'a when 'a:comparison
  val maxBy : ('a -> 'b) -> t<'a> -> 'a when 'b:comparison
  val nonempty : t<'a> -> bool
  val nth : t<'a> -> int -> 'a
  val fromArray : 'a array -> t<'a>
  val toArray : t<'a> -> 'a array
  val fromSeq : seq<'b> -> t<'b>
  val toSeq : t<'a> -> seq<'a>
  val partition : ('a -> bool) -> t<'a> -> t<'a> * t<'a>
  val permute : (int -> int) -> t<'a> -> t<'a>
  val pick : ('a -> option<'b>) -> t<'a> -> 'b
  val reduce : ('a -> 'a -> 'a) -> t<'a> -> 'a
  val reduceBack : ('a -> 'a -> 'a) -> t<'a> -> 'a
  val replicate : int -> 'a -> t<'a>
  val rev : t<'a> -> t<'a>
  val scan : ('a -> 'b -> 'a) -> 'a -> t<'b> -> t<'a>
  val scanBack : ('a -> 'b -> 'b) -> t<'a> -> 'b -> t<'b>
  val sort : t<'a> -> t<'a> when 'a: comparison
  val sortBy : ('a -> 'b) -> t<'a> -> t<'a> when 'b: comparison
  val sortWith : ('a -> 'a -> int) -> t<'a> -> t<'a>
  val tail : t<'a> -> t<'a>
  val tryFind : ('a -> bool) -> t<'a> -> option<'a>
  val tryFindIndex : ('a -> bool) -> t<'a> -> option<int>
  val tryPick : ('a -> 'b option) -> t<'a> -> option<'b>