Extracting a common interface for Stacks and Queues

Question

I'm would like to compare the performance of two heuristics for a game AI that I am working on. One processes elements in FIFO order; the other in LIFO order.

As it stands, the code uses a Queue to process element in FIFO order. In OOP I would have a Bag interface implemented by both Stack and Queue, and I would use Bag.push and Bag.take to interact with the structure. Then I would assign the result of either Stack.create () or Queue.create () to a variable of type Bag, based on the value of a command line flag, for example.

I know how to replicate similar behavior in OCaml using abstract classes and constraining types with :>. However, I imagine that there might be a cleaner way to do this, that wouldn't require writing wrapper classes around Queue and Stack.

I tried something like

module type Bag =
sig
    type 'a t
    exception Empty
    val create : unit -> 'a t
    val push : 'a -> 'a t -> unit
    val iter : ('a -> unit) -> 'a t -> unit
end

module BagWrapper (B : Bag) = 
struct
    type 'a t = 'a B.t
    let create () = B.create ()
    let push a b = B.push a b
    let iter a b = B.iter a b
end 

module QueueBag = BagWrapper(Queue)
module StackBag = BagWrapper(Stack)

...but I'm not sure what to do next. Ideas?

Answer 1

ygrek solution using first-class modules to decide "dynamically" (on a boolean value) the value of the Bag module is fine, but you can also do that in simpler OCaml by simply defining your traversal algorithm inside a functor taking a bag as parameter.

module type Bag =
sig
    type 'a t
    exception Empty
    val create : unit -> 'a t
    val push : 'a -> 'a t -> unit
    val pop : 'a t -> 'a
    val iter : ('a -> unit) -> 'a t -> unit
end

module Traversal (B : Bag) = struct
  let go start children f =
    let to_visit = B.create () in
    B.push start to_visit;
    try while true do
      let next = B.pop to_visit in
      f next;
      let mark neighbor = B.push neighbor to_visit in
      List.iter mark (children next);
    done with B.Empty -> ()
end;;

(* note that "BagWrapper" is useless here as the existing modules
   fit the Bag interface perfectly, there is no need for a middle
   layer *)
module StackTraversal = Traversal(Stack)
module QueueTraversal = Traversal(Queue)


(* ... if foo then StackTraversal.go else QueueTraversal.go ... *)

Answer 2

Ok, so you want to write

let module Bag = if use_queue then QueueBag else StackBag in
some algorithm

but OCaml won't let you do it..

First-class modules to the rescue!

let m = if use_queue then (module QueueBag : Bag) else (module StackBag : Bag) in
let module Bag = (val m : Bag) in

This looks rather verbose, fortunately newer OCaml versions let you drop some type annotations in this case.