Модули OCaml: перенос (взаимосвязанных) типов из разных модулей в новый модуль

Проблема

Одна проблема, с которой я столкнулся, заключается в том, чтобы привести типы и значения двух модулей в новый комбинированный модуль. Я приведу пример. В настоящее время у меня есть следующие подписи двух типов

module type Ordered =
 sig
  type t (* the type of elements which have an order *)
  val eq : t * t -> bool
  val lt : t * t -> bool
  val leq : t * t -> bool
 end

module type Stack =
 sig
  exception Empty 
  type 'a t (* the type of polymorphic stacks *)

  val empty  : 'a t
  val isEmpty : 'a t -> bool

  val cons  : 'a * 'a t -> 'a t
  val head  : 'a t -> 'a
  val tail  : 'a t -> 'a t
 end

и я хотел бы создать модуль «стеков, для которых упорядочены основные элементы», т.е.

module type OrderedStack =
 sig 
  exception Empty

  type elem (* the type of the elements in the stack *)
  val eq : elem * elem -> bool
  val lt : elem * elem -> bool
  val leq : elem * elem -> bool

  type t (* the type of monomorphic stacks *)
  val empty  : t
  val isEmpty : t -> bool
  val cons  : elem * t -> t
  val head  : t -> elem
  val tail  : t -> t
 end

До сих пор все красиво и аккуратно. Но теперь я хотел бы написать функтор, который берет модуль Ordered и модуль Stack и создает модуль OrderedStack. Что-то типа

module My_functor (Elem : Ordered) (St : Stack): OrderedStack  = 
 struct
  exception Empty

   type elem = Elem.t
  let eq = Elem.eq
  let lt = Elem.lt
  let leq = Elem.leq

  type t = elem St.t
  let empty = St.empty
  let isEmpty = St.isEmpty
  let cons = St.cons
  let head = St.head
  let tail = St.tail
 end

Это именно то, что я хочу, и это правильно. Но это выглядит как ужасная трата клавиатуры.

Мой вопрос

Есть ли более компактный способ написать My_functor выше?

Что я узнал, но не смог применить

Я видел директиву include, в которой я мог бы написать что-то вроде:

module my_functor (Elem : Ordered) (St : Stack): OrderedStack  = 
 struct
  include Elem
  include St
 end

но проблема в том, что для моих конкретных двух модулей выше и Ordered, и Stack имеют одинаковые type t (хотя в каждом из них они означают разные вещи). Я бы предпочел не менять исходное определение Ordered и Stacks, так как они уже используются во многих частях кода, но если вы найдете альтернативную формулировку для исходных двух модулей, которая заставит их работать, это нормально.

Я также видел, что оператор with может быть уместным здесь, но я не мог понять, как его следует использовать для получения желаемого эффекта. Проблема, с которой я столкнулся, заключается в том, что типы t и 'a t двух модулей Ordered и Stacks действительно подключены.

Любые идеи?


person Surikator    schedule 29.01.2011    source источник
comment
Я добавил решение OCaml 3.12, которое позволяет включать как MonoStack, так и Ordered вместо подмодулей. Однако я предпочитаю решение с подмодулями - по крайней мере, потому, что я еще не использую 3.12. Одна приятная вещь с подмодулями заключается в том, что вы можете легко передать их другим функторам: о, мне нужно построить Set из элементов моего стека.   -  person gasche    schedule 30.01.2011
comment
@gasche Да, у меня тоже нет 3.12. И я бы предпочел не спешить с изменением кода до самых последних изменений языка, поскольку он не будет компилироваться на других машинах, если у вас нет современных установок. Да, вы правы, я не думал о такой возможности использовать части модуля в функторах. Довольно аккуратно!   -  person Surikator    schedule 30.01.2011


Ответы (1)


OrderedStack повторно использует упорядоченные определения с немного другим типом (elem вместо t). Это причина избыточности.

Вы могли бы использовать эту подпись OrderedStack напрямую, повторно используя Ordered :

module type OrderedStack = sig
    module Elem : Ordered

    type t
    val empty       : t
    val isEmpty     : t -> bool
    val cons        : Elem.t * t -> t
    val head        : t -> Elem.t
    val tail        : t -> t
end

Еще одним источником избыточности является тот факт, что вы переходите от параметрического типа 'a Stack.t к мономорфному OrderedStack.t. Эти два типа нельзя отождествлять, они вообще не сопоставимы, поэтому здесь обязательно нужно делать перевод вручную.

Обратите внимание, что вы можете разложить переход от (полиморфного) Stack к OrderedStack в один промежуточный стек (мономорфный) MonoStack:

module type MonoStack = sig
  type elem
  type t
  val empty       : t
  val isEmpty     : t -> bool
  val cons        : elem * t -> t
  val head        : t -> elem
  val tail        : t -> t
end

module type OrderedStack = sig
  module Elem : Ordered
  module Stack : MonoStack with type elem = Elem.t
end

Изменить

Если вам не нравится дополнительная косвенность использования подмодулей, которая может добавить некоторую синтаксическую нагрузку, можно включить модули вместо ссылки на них. Но проблема, как вы заметили, заключается в конфликте имен. Начиная с OCaml 3.12, в нашем наборе инструментов появилась новая конструкция, которая позволяет переименовывать компоненты типа подписи, чтобы избежать конфликтов.

module type OrderedStack = sig
  type elem
  include Ordered with type t := elem
  include MonoStack with type elem := elem
end

Второе редактирование

Хорошо, я придумал следующее решение, чтобы поставить мост Stack/MonoStack. Но, честно говоря, это хак, и я не думаю, что это хорошая идея.

module type PolyOrderedStack = sig
  module Elem : Ordered
  type t
  type 'a const = t
  module Stack : Stack with type 'a t = 'a const
end

(* 3.12 only *)
module type PolyOrderedStack = sig
  type elem
  include Ordered with type t := elem
  type t
  type 'a const = t
  include Stack with type 'a t := 'a const
end
person gasche    schedule 29.01.2011
comment
Я не зря перешел с полиморфного стека на мономорфный. Обратите внимание, что в моем OrderedStack, если бы я использовал тип стека 'a t, у меня был бы параметр, которого я не мог бы иметь. Стек будет представлять собой стек элементов типа elem, т.е. в OrderedStack есть связь между типом Ordered и типом Stack. Итак, чтобы следовать вашей идее декомпозиции, я был бы рад использовать Stack напрямую вместо MonoStack. Но что бы вы написали в последней строке кода типа OrderedStack? Вы не могли написать module Stack : Stack with type 'a t = Elem.t... - person Surikator; 30.01.2011
comment
Спасибо за решение, связанное с подмодулями. Это аккуратно. Есть только одна вещь, которая мне в этом не нравится. В этой формулировке, когда мне нужно сравнить два элемента с помощью модуля OS : OrderedStack, мне придется писать OS.Elem.leq (x,y) вместо простого OS.leq (x,y), что кажется немного неестественным. Кроме того, если я просто хочу поместить что-то в стек, я бы написал OS.Stack.cons (x,s), тогда как я хотел бы использовать ОС напрямую с OS.cons (x,s). Сказав это, я бы обязательно остановился и подумал, какую именно внутреннюю структуру я использую при сравнении элементов или при нажатии. - person Surikator; 30.01.2011
comment
(в редакции 3.12) Отличный материал! Это именно то, что я хотел, да. Я не знал об этой конструкции. Очень интересно. Спасибо! (Единственная проблема сейчас в том, что я использую Godi, который на данный момент имеет только 3.11.2. Надеюсь, скоро будет обновлено.) - person Surikator; 30.01.2011
comment
Нет, но подожди. Это для подписи (тип модуля). Как мне написать функтор? Я не могу использовать include в модулях или функторах. - person Surikator; 30.01.2011
comment
Хорошо, тогда для функторов я буду использовать подмодули. Мне на самом деле постепенно нравится это решение больше. Включает немного грязно. Мономорфизм/полиморфизм все еще действует мне на нервы. Должен быть способ сделать это. Ваша 'a cons идея решает проблему, но, как и вы, я считаю, что взлом может привести к неясному ядру. - person Surikator; 30.01.2011