Strange Confluence: An Immutable Queue in F#

Strange Confluence: An Immutable Queue in F#

  • Comments 3

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> =

        new()={xs=[];rxs=[]}

        new(xs,rxs)={xs=xs;rxs=rxs}

       

        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.

Leave a Comment
  • Please add 2 and 4 and type the answer here:
  • Post
  • You should update your blog title to include F#

  • 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?

  • **Slap-head**

    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!

Page 1 of 1 (3 items)