Duplicate values in Ocaml

Question

How do you delete repeated values (i.e. duplicates) from a queue in Ocaml?

For example, suppose this is a queue (although it is presented in the form of a list):

     [1; 1; 2; 3; 4; 7; 7; 8; 8; 8]

Then, after applying this function to the queue, we would get:

     [1; 2; 3; 4; 7; 8]

Implementation in the case of lists:

     let rec deleteDuplicate l = 
        match l with 
         | []                -> [] 
         | x :: []          -> x :: [] 
         | x :: y :: rest -> 
               if x = y then deleteDuplicate (y :: rest) 
               else x :: deleteDuplicate (y :: rest) 

Answer 1

I think the first thing to do is to decide how you're going to represent your queues. You can use the Queue module that's part of the standard OCaml library. This uses a mutable representation for the queue. Or you can use a very nice (simple but clever) immutable representation that consists of two lists, one for the head and a reversed one for the tail. After you decide on your representation, I suspect it will be easy to see what to do. You had no trouble doing it for a list.

Let's say you want to use the Queue module from the OCaml library. Since this is a mutable queue, I'll assume you want to code in imperative style. I.e., you want to modify an existing queue so that duplicates are removed.

One very straightforward way to do this is to transform to a list first, then apply your function to the list, then put the elements back into the queue.

let rec list_of_queue q =
    (* Change queue to list, emptying queue in the process.
     *)
    if Queue.is_empty q then [] else let h = Queue.take q in h :: list_of_queue q

let queue_add_list q l =
    List.iter (fun x -> Queue.add x q) l

let deleteQueueDuplicates q =
    let l = list_of_queue q in
    queue_add_list q (deleteDuplicate l)