Implement a queue type in F# contains elements

Question

I'm implement a queue in F# and works good inserting the elements.

// Defines the Queue type as an algebraic data type.
type 'a Queue = QueueList of 'a list * 'a list

let empty = QueueList([], [])

let add elem = function
  | QueueList(top, rest) -> QueueList(top, elem :: rest)

I'm stuck trying to verify that if the queue list has the element, return true. If not return false.

// Returns true if the queue contains the given element.
val contains: 'a -> 'a Queue -> bool when 'a : equality

// Returns true if the queue contains the given element.
// let rec contains elem = function
       | QueueList([], []) -> false
       | QueueList(hd::tl, tl2) -> if hd = elem 
                                       then true 
                                         else contains elem (QueueList (tl, tl2))

Thanks for the help.

user_338059 · Answer

You could implement an immutable queue by using the idea of a list. So you have a top element and the rest of your Queue.

type QueueA<'a> =
    | Empty
    | Top   of 'a * QueueA<'a>

This is possible; but has bad performance for insertion. Anyway here is how you could implement this kind of Queue.

module QueueA =
    let empty = Empty

    let rec add x q =
        match q with
        | Empty        -> Top (x,Empty)
        | Top(y,rest ) -> Top (y, add x rest)

    let head q =
        match q with
        | Empty       -> None
        | Top(x,rest) -> Some x

    let tail q =
        match q with
        | Empty       -> None
        | Top(x,rest) -> Some rest

    let rec iter f q =
        match head q with
        | None   -> ()
        | Some x ->
            f x
            Option.iter (iter f) (tail q)

The add is not tail-recursive. If you want that the first element stays at the top and further added elements added to the end then you must rebuild the whole Queue. Add is basically a List.append where you add an element to the end of the queue rebuilding the whole Queue. So you have slow insertion with quadratic O(x^2) performance.

But tail is a fast operation with O(1).

Instead of doing this, you can use two lists for an immutable queue. The idea is: Added elements build a list and you leave them at the reverse order as long as you don't fetch an element. Only if you want to fetch an element, and no reversed list is avaiable you reverse the list once, and save the reversed list. So adding an element is O(1) performance.

Fetching an element on the other-side can be O(1) if you already have an reversed list or O(N) if not. Usually you could say it is Amortized O(1).

An implementation looks like

type QueueB<'a> = Queue of queue:list<'a> * added:list<'a>

module QueueB =
    let empty     = Queue ([], [])
    let queue q a = Queue (q,a)

    let add x (Queue (q,r)) =
        queue q (x::r)

    let head q =
        match q with
        | Queue([],[]) -> None
        | Queue([],r)  -> Some (List.head (List.rev r))
        | Queue(q,_)   -> Some (List.head q)

    let tail q =
        match q with
        | Queue([],[]) -> None
        | Queue([],r)  ->
            let q = (List.tail (List.rev r))
            Some (queue q [])
        | Queue(h::t,r) ->
            Some (queue t r)

    let rec iter f q =
        match head q with
        | None   -> ()
        | Some x ->
            f x
            Option.iter (iter f) (tail q)

For example when you add 1,2,3 to QueueA, it will Build the structure

Top(1, Top(2, Top(3, Empty)))

When you add 1,2,3 to QueueB, it will Build the structure

Queue([], [3;2;1])

When you call tail on this you get

Queue([2;3], [])

Adding 4,5,6 yields

Queue([2;3], [6;5;4])

Examples

(* Top(1, Top(2, Top(3, Empty))) *)
let qs =
    QueueA.empty
    |> QueueA.add 1
    |> QueueA.add 2
    |> QueueA.add 3

(* Queue([], [3;2;1]) *)
let qs =
    QueueB.empty
    |> QueueB.add 1
    |> QueueB.add 2
    |> QueueB.add 3

(* Queue([2;3], [6;5;4]) *)
let qs2 =
    QueueB.tail qs
    |> Option.defaultValue QueueB.empty
    |> QueueB.add 4
    |> QueueB.add 5
    |> QueueB.add 6

(* Prints numbers from 2 to 6 *)
QueueB.iter (printfn "%d") qs2

Maybe in a real implementation I would change head to also return the remaining Queue (the tail). Because most of the time you probably also will call tail if you use head. And in this case, the reversing of the list happens twice.

Returning both with head only does this once. If you don't need the tail, then you can just throw the tail away.

Now, if you want additional functions, you should add a fold and foldBack function first. For example on QueueB a fold will be

let rec fold f (state:'State) q =
    let rec loop state q =
        match head q with
        | None      -> state
        | Some head ->
            match tail q with
            | None      -> state
            | Some rest -> loop (f state head) (rest)
    loop state q

Then you can implement contains with it.

let contains x q =
    let folder state e =
        if e = x then true else state
    fold folder false q

And with the qs2 from above

QueueB.contains 1 qs2 (* false *)
QueueB.contains 6 qs2 (* true  *)

Implement a queue type in F# contains elements

1 Answers