Strange Confluence: An Immutable Queue in F#

Jomo Fisher–Reading one of my favorite blogs this morning–Eric Lippert’s Fabulous Adventures in Coding–I came across his article on implementing an immutable queue in C#. The funny thing is that just yesterday I wrote exactly the same structure in F#. Here it is for your reading pleasure:

    type Fifo<‘a> =




        val xs: ‘a list;

        val rxs: ‘a list;


        static member Empty() = new Fifo<‘a>()

        member q.IsEmpty = (q.xs = []) && (q.rxs = [])

        member q.Enqueue(x) = Fifo(q.xs,x::q.rxs)

        member q.Take() =

            if q.IsEmpty then failwith “fifo.Take: empty queue”

            else match q.xs with

                    | [] -> (Fifo(List.rev q.rxs,[])).Take()

                    | y::ys -> (Fifo(ys, q.rxs)),y

This is code modified from a mutable structure that I found in the F# distribution. The queues are pretty similar except for a few minor details:

  • F# version doesn’t implement IEnumerable<T>.

  • F# version relies on the built-in list class which is semantically identical to an immutable stack.

  • C# version carries the “popped” instance of T along with the queue itself whereas the F# version returns this as part of a tuple from Take(). I think I prefer my way on this point–it seems like information leakage for the queue have a memory of the last thing popped.

That’s all for now, and as always…


This posting is provided “AS IS” with no warranties, and confers no rights.

Comments (3)

  1. Wife says:

    You should update your blog title to include F#

  2. Matt Warren says:

    Thanks so much for these F# blog entries, they’ve been really useful.

    Am I mis-understanding this queue, is xs the queue and rxs the queue reversed? Should rxs always = List.rev(xs)?

    If so why does the Enqueue function not add an item to both lists, shouldn’t it be this?

    member q.Enqueue(x) = Fifo(q.xs::x, x::q.rxs)

    Or am I missing something?

  3. Matt Warren says:


    Just look a better look at the Take() function and realised that you take from the xs queue until it’s empty and then fill it with a reversed version of the rxs queue.

    It makes sense now, so you can ignore my last msg!