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:
That's all for now, and as always...
This posting is provided "AS IS" with no warranties, and confers no rights.
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?
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!