Hi Julien,

A discriminated union might also be a good fit for an immutable Queue implementation, e.g.:

/// Generic immutable batched queue type

type BatchedQueue<'a when 'a: comparison> =

BatchedQueue of 'a list * 'a list

with

/// Return an empty queue

static member empty : BatchedQueue<'a> = BatchedQueue([],[])

/// Return true if the queue contains no elements, false otherwise

static member isEmpty : BatchedQueue<'a> -> bool = function

| BatchedQueue([],[]) -> true

| BatchedQueue(_,_) -> false

member this.IsEmpty () = BatchedQueue.isEmpty this

/// Create queue in normal form

static member private norm(f:'a list,r:'a list) =

match f,r with

| ([],r) -> BatchedQueue(List.rev r,[])

| (f,r) -> BatchedQueue(f,r)

/// Cons on the right

static member snoc (q:BatchedQueue<'a>,x:'a) =

match q with

| BatchedQueue(f,r) -> BatchedQueue.norm(f,x::r)

/// Return the first element of the queue

static member head : BatchedQueue<'a> -> 'a = function

| BatchedQueue([],_) -> invalidOp "EMPTY"

| BatchedQueue(x::f,r) -> x

/// Return the tail of the queue

static member tail : BatchedQueue<'a> -> BatchedQueue<'a> = function

| BatchedQueue([],_) -> invalidOp "EMPTY"

| BatchedQueue(x::f,r) -> BatchedQueue.norm(f,r)

/// Build a list from the given queue

static member toList : BatchedQueue<'a> -> List<'a> = function

| BatchedQueue(f,r) -> List.append f (List.rev r)

A mutable Queue similar to the .Net Framework's System.Collections.Generic.Queue<T> can then be implemented as a class type:

/// Generic mutable queue type

type Queue<'a when 'a: comparison> () =

let mutable queue = BatchedQueue.empty

member this.IsEmpty = queue.IsEmpty

member this.Enqueue x =

queue <- BatchedQueue.snoc (queue,x)

member this.Dequeue () =

let x = BatchedQueue.head queue

queue <- BatchedQueue.tail queue

x

interface System.Collections.Generic.IEnumerable<'a> with

member this.GetEnumerator() =

(BatchedQueue.toList queue |> List.toSeq).GetEnumerator()

interface System.Collections.IEnumerable with

member this.GetEnumerator() =

let xs = BatchedQueue.toList queue |> List.toSeq

xs.GetEnumerator() :> System.Collections.IEnumerator

Hope this helps,
Phil

P.S. The BatchedQueue implementation is based on code in the book Purely Functional Data Structures by Chris Okasaki (Page 42).