CODEWITHSUNDEEP
functional-programmingocaml
qiubit
qiubit

Reputation: 4816

Unbound module type in queue implementation

I'm trying to implement double-ended queue in OCaml. Here is a code I came up with (it's in 2 files - interface in queue.mli and implementation in queue.ml)

module type QUEUE = 
    sig
        type 'a queue
        exception EmptyQueue
        val empty : 'a queue
        val is_empty : 'a queue -> bool
        val push_front : 'a -> 'a queue -> 'a queue
        val push_back : 'a -> 'a queue -> 'a queue
        val remove_front : 'a queue -> ('a * 'a queue)
        val remove_back : 'a queue -> ('a * 'a queue)
    end;;

-

module Queue : QUEUE = struct

    type 'a queue = {front : 'a list; back : 'a list; size : int}

    exception EmptyQueue

    let empty = {front = []; back = []; size = 0}

    let is_empty q = if (q.front = [] && q.back = []) then true else false

    let make_split l i =
        let rec aux l nl i =
            if i = 0 then
                (List.rev nl, l) else
            match l with
            | [] -> failwith "Something went wrong"
            | h :: t -> aux t (h :: nl) (i - 1)
        in aux l [] i

    let balance q =
        if is_empty q then q else
        if q.front = [] then
            let iterator = (q.size / 2) in
            let (qfront, qback) = make_split q.back iterator in
            {front = qfront; back = qback; size = q.size} else
        if q.back = [] then
            let iterator = (q.size / 2) in
            let (qback, qfront) = make_split q.front iterator in
            {front = qfront; back = qback; size = q.size}
        else q

    let push_front e q =
        let q1 = {front = e :: q.front; back = q.back; size = q.size + 1} in
        balance q1

    let push_back e q =
        let q1 = {front = q.front; back = e :: q.back; size = q.size + 1} in
        balance q1

    let remove_front q =
        if is_empty q then raise EmptyQueue else
        if q.size = 1 then
          match (q.front, q.back) with
          | ([], h :: t) -> (h, empty)
          | (h :: t, []) -> (h, empty)
          | (_, _) -> failwith "Something went wrong"
        else
            let q1 = balance q in
            let value = List.hd q1.front in
            (value, {front = List.tl q1.front; back = q1.back; size = q.size - 1})

    let remove_back q =
        if is_empty q then raise EmptyQueue else
        if q.size = 1 then
          match (q.front, q.back) with
          | ([], h :: t) -> (h, empty)
          | (h :: t, []) -> (h, empty)
          | (_, _) -> failwith "Something went wrong"
        else
            let q1 = balance q in
            let value = List.hd q1.back in
            (value, {front = q1.front; back = List.tl q1.back; size = q.size - 1})
    end;;

The problem is, it won't compile. When trying to use ocamlc -c queue.mli queue.ml OCaml compiler returns an error - File "queue.ml", line 1, characters 15-20: Error: Unbound module type QUEUE. I can't see why that's the case as I defined type QUEUE in queue.mli. So, what is going on?

Upvotes: 0

Views: 1309

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66813

I think the problem is that you have to think of queue.mli as a subset of queue.ml, rather than something that gets added to queue.ml. In practice what this means is that the definition of QUEUE has to appear in queue.ml as well as in queue.mli. There are advantages to this layout, but it's often a little redundant.

Upvotes: 2

Related Questions