Извлечение общего интерфейса для стеков и очередей

Question

Я хотел бы сравнить производительность двух эвристик для игрового ИИ, над которым я работаю. Один обрабатывает элементы в порядке FIFO; другой в порядке LIFO.

В порядке вещей, код использует Queue для обработки элемента в порядке FIFO. В ООП у меня был бы интерфейс Bag, реализованный как Stack, так и Queue, и я бы использовал Bag.push и Bag.take для взаимодействия со структурой. Тогда я бы присвоил результат Stack.create() или Queue.create() переменной типа Bag, в зависимости от значения флага командной строки, например.

Я знаю, как копировать подобное поведение в OCaml, используя абстрактные классы и ограничивающие типы с помощью :>. Однако я полагаю, что может быть более чистый способ сделать это, что не потребует писать классы обертки вокруг Queue и Stack.

Я пытался что-то вроде

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) 

... но я не уверен, что делать дальше. Идеи?

Answer 1

решение YGREK с использованием модулей первого класса, чтобы решить «динамически» (на логическое значение) значение Bag модуля хорошо, но вы также можете сделать , что в простом OCaml, просто определив свой алгоритм обхода внутри функтор берёт мешок в качестве параметра.

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, так что вы хотите написать

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

но OCaml не позволит вам это сделать ..

First-class modules на помощь!

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

Это выглядит довольно многословно, к счастью, более новые версии OCaml позволяют отбросить некоторые аннотации типа в этом случае.