Рекурсивный набор в OCaml - PullRequest
Новая
       17

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

5 голосов
/ 11 июля 2010

Как мне определить 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 модуль decl, так как я не уверен, что это возможно).

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

1 Ответ

6 голосов
/ 12 июля 2010

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

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

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
...