CODEWITHSUNDEEP
functional-programmingqueueocamlfifoabstract-data-type
imalgrab
imalgrab

Reputation: 23

Queue on List in OCaml

I have to implement an abstract data type, it has to be Queue, which matches this signature:

module type QUEUE_FUN =
sig
  (* Module [QueueFun]: first-in first-out queues *)

  (* This module implements queues (FIFOs)in a functional way. *)

  type 'a t
        (* The type of queues containing elements of type ['a]. *)
  exception Empty of string
        (* Raised when [first] is applied to an empty queue. *)
  val create: unit -> 'a t
        (* Return a new queue, initially empty. *)
  val enqueue: 'a * 'a t -> 'a t
        (* [enqueue x q] adds the element [x] at the end of queue [q]. *)
  val dequeue: 'a t -> 'a t
        (* [dequeue q] removes the first element in queue [q] *)        
  val first: 'a t -> 'a
        (* [first q] returns the first element in queue [q] without removing  
           it from the queue, or raises [Empty] if the queue is empty.*) 
  val isEmpty: 'a t -> bool
        (* [isEmpty q] returns [true] if queue [q] is empty, 
           otherwise returns [false]. *)
end;;

It also needs to be done on a List, so I tried this:

module Queue_B : QUEUE_FUN =
  struct
    type 'a t = List of 'a
    exception Empty of string
    let create() = []
    let enqueue(x, q) = [x] @ q
    let dequeue = function
        [] -> []
      | h::t -> t
    let first = function
        [] -> raise (Empty "module Queue: first")
      | h::t -> h
    let isEmpty q = q = []
  end;;

But I cannot figure it out how to make a proper type and I have this error:

Error: Signature mismatch:
       ...
       Values do not match:
         val create : unit -> 'a list
       is not included in
         val create : unit -> 'a t

What should I do then? It has to be done on a List.

Upvotes: 0

Views: 1337

Answers (1)

imalgrab
imalgrab

Reputation: 23

Ok, I've simply tried:

type 'a t = 'a list

And it's working fine right now

Upvotes: 1

Related Questions