Simple queue on F#

Question

namespace DataStructures

type Queue<'T>() =
    let mutable _list  : List<'T> = []
    let mutable _count : int = 0

    member this.Enqueue value =
        let revList = List.rev _list
        _list  <- List.rev (value :: revList)
        _count <- _count + 1

    member this.Dequeue =
        match _list with
        | result :: remainder -> 
            _list  <- remainder
            _count <- _count - 1
            result
        | [] -> failwith "Queue is empty"

    member this.Count = _count

    member this.IsEmpty = _count = 0

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

        member this.GetEnumerator() = 
            let e = seq {
                yield! _list
            }
            e.GetEnumerator()

        member this.GetEnumerator() =
            (this :> _ seq).GetEnumerator()
            :> System.Collections.IEnumerator

That's simple implementation of queue on f#. I'm new in f#. I want to know how to do this code better, make it more functional and what's wrong in my implementation.

Answer 1

Hi this is my first post and answer on CodeReview and I hope the following makes sense.

There has been no answer for a year and I presume you have learnt and moved on. Still there are some classic noobie mistakes here, that we all go through on a functional learning curve, so I hope this provides some value to others.

1. Use of mutable A typical challenge for someone new to F#, say coming from C#, is to use mutable identifiers. Indeed better to think of let as an identifier rather than variable assignment. The use of the mutable keyword is meant to be awkward and non-default to help highlight this. So a key challenge is to find an immutable way of working here, if possible, in this case it is. The usual method is to return the updated/new data structure as part of the function result, in a tuple.

2. Double use of List.rev in Enqueue. This is another clue. Using a List - a singly linked list with \$O(1)\$ cons - is good but List.rev is \$O(n) x 2\$ here. And you need a mutable reference to the changed list rather than generating a new list. The beauty of F# list is to generate a new instance of a type with a cons for which the old list is not altered. Further, it is clear that one list will not suffice, this is not a stack. Maybe two lists might do? But how to manage them?

3. Optional - there is no reason not to use a class as you have here and many sophisticated data structures can be accessed better in such a class. However this is quite a simple data structure and you should not need to use a class and this might also distract from the essence of the challenge. Further the more functional way means that you will be, as already noted in 2, returning the updated data structure for all your functions, and this is more naturally seen first outside a class.

4. Putting this all together the key theme is to how use two lists and immutability to solve your challenge. I will not address question over this as a class nor enumerations in this answer.

So you can have 1 list to enqueue (using cons) and one to dequeue (using decapitation) but how do they relate. Looks like you will have to use List.rev to as little as possible to maximise \$O(1)\$ operations and minimise \$O(n)\$ operations. I imagine you would end up with something like this:

First you need a different type and not a class;

type queue<'a> = | Queue of 'a list * 'a list

a single case discriminated union containing two lists in a tuple. This DU gives you a constructor for free:

let create = Queue([], [])

Enqueue is the simple one, cons to the front list. Note that since a new list is generated the enqueue must return a new version of the type, this way you don't need mutable lets, but it does change your public interface. The Queue instance is implicit and deconstructed by function and the DU makes this deconstruction clear.

let enqueue e = function Queue(fl, bl) -> Queue(e :: fl, bl)

(The type signature here is 'a -> Queue<'a,'a> -> Queue<'a,'a> )

The real challenge is to dequeue. It should be clear that one decapitates the back list for the result. The challenge is to see how the two lists can be related and update each other. This is shown in the final case in the following pattern match, when the back list is empty (either after some dequeues or before any dequeues) then, and only then, do you need to reverse the front list:

let dequeue = function 
    | Queue([], []) -> failwith "Empty"
    | Queue(fl, b :: bl) -> b, Queue(fl, bl)
    | Queue(fl, []) -> 
        let bl = List.rev fl
        List.head bl, Queue([], List.tail bl)

For count and empty we have:

let count = function Queue(fl,bl) -> List.length bl + (List.length fl)
let empty = function Queue([],[]) -> true | _ -> false

so no need to keep track of the count with a mutable.

P.S. If you do implement the IEnumerable<'T> interface for a type you change your yield from:

yield! _list

to following the order in which this would be dequeued :

yield! bl
yield! List.rev fl