Рекурсивный набор в OCaml

как я могу определить Set в OCaml, который также может содержать элемент его типа?

Чтобы объяснить проблему, у меня есть объявление типа для многих типов данных, таких как

type value =
  Nil
| Int of int
| Float of float
| Complex of Complex.t
| String of string
| Regexp of regexp
| Char of char
| Bool of bool
| Range of (int*int) list
| Tuple of value array
| Lambda of code
| Set of ValueSet.t (* this isn't allowed in my case since module is declared later*)

Кроме того, я объявлю конкретный модуль для ValueSet позже в том же файле:

module ValueSet = Set.Make(struct type t = value let compare = Pervasives.compare end)

Проблема в том, что ValueSet имеет value в качестве типа elt, но value может быть ValueSet, поэтому у меня возникают проблемы при попытке его скомпилировать.

Все эти объявления содержатся только в файле с именем types.ml (у которого есть собственный интерфейс types.mli, но без какого-либо объявления модуля ValueSet, поскольку я тоже не уверен, что это возможно).

Можно ли как-то решить эту проблему?


module recursion ocaml
person Jack    schedule 11.07.2010    source источник

Ответы (1)


arrow_upward
7
arrow_downward

Вы можете использовать рекурсивные модули. Руководство по языку использует точно такой же пример рекурсивного типа набора, чтобы проиллюстрировать эту языковую функцию. Ниже приводится соответствующий отрывок.

Типичный пример определения рекурсивного модуля:

module rec A : sig
                 type t = Leaf of string | Node of ASet.t
                 val compare: t -> t -> int
               end
             = struct
                 type t = Leaf of string | Node of ASet.t
                 let compare t1 t2 =
                   match (t1, t2) with
                     (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
                   | (Leaf _, Node _) -> 1
                   | (Node _, Leaf _) -> -1
                   | (Node n1, Node n2) -> ASet.compare n1 n2
               end
    and ASet : Set.S with type elt = A.t
             = Set.Make(A)

Ему можно дать следующую спецификацию:

module rec A : sig
                 type t = Leaf of string | Node of ASet.t
                 val compare: t -> t -> int
               end
    and ASet : Set.S with type elt = A.t
person rkhayrov    schedule 11.07.2010
comment
Похоже, мой компилятор OCaml (3.11.0) их еще не поддерживает. В любом случае наличие такого рекурсивного объявления внутри types.ml приведет к необходимости наличия внутренних модулей, таких как Types.InnerTypes и Types.ValueSet, что может быть приемлемым для ValueSet, но не для другого .. - person Jack; 12.07.2010
comment
Я думаю, что постепенно у меня все получается ... Я, наверное, скоро приму твой ответ, если смогу заставить его работать :) - person Jack; 12.07.2010
comment
OCaml имеет рекурсивные модули с 3.07. - person Gilles 'SO- stop being evil'; 17.07.2010