Freigeben über

Strange Confluence: An Immutable Queue in F#

  • Artikel

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.

Comments

  • Anonymous
    December 13, 2007
    You should update your blog title to include F#

  • Anonymous
    January 28, 2010
    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?

  • Anonymous
    January 28, 2010
    The comment has been removed