CODEWITHSUNDEEP
genericsocaml
jyshin
jyshin

Reputation: 891

Generic type implementation in OCaml

Is there a way to implement Queue supporting heterogeneous type like generic type in Java or C#?

Below is a module type for Queue.

module type Queue = 
sig
  type element
  type queue
  exception EMPTY_Q
  val emptyq: queue
  val enq: queue * element -> queue
  val deq: queue -> element * queue
end

If I want to implement string queue I would type the codes like this.

module StringQ : Queue with type element = string = 
struct 
  type element = string
  type queue = (* queue type *)
  exception EMPTY_Q
  let emptyq: queue = (* empty queue *)
  let enq: queue * element -> queue = 
    (* enqueue logic *)
  let deq: queue -> element * queue = 
    (* dequeue logic *)
end

And that, If I need to implement integer queue, is there a way to implement that without copy and paste upper enq, deq logic?

I think both enq, deq logics would be identical regardless of element type.

Upvotes: 1

Views: 3084

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66813

You can write a polymorphic queue:

exception EMPTY_Q
type 'a q = Q of 'a list * 'a list
let pq_empty = Q ([], [])
let pq_enqueue (Q (a, b)) c = Q (a, c :: b)
let rec pq_dequeue (Q (a, b)) =
    match a, b with
    | [], [] -> raise EMPTY_Q
    | [], _ -> pq_dequeue (Q (List.rev b, []))
    | h :: t, _ -> (h, Q (t, b))

You can also write a functorial queue, i.e., a module parameterized by the type of the queue element.

There's no need to write code for each different element type in either case.

However in both cases the queues would be homogeneous, i.e., all elements of any one queue are of the same type.

Upvotes: 4

Related Questions