# Is there any way to write recursive module types?

**URL:** <https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045>\
**Category:** Learning\
**Tags:** type-system, module, recursion\
**Created:** [January 4, 2021, 9:20am UTC](https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045 "2021-01-04T09:20:34Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![davidw](https://avatars.discourse-cdn.com/v4/letter/d/c4cdca/32.png) [@davidw](https://discuss.ocaml.org/u/davidw)\
**Post date:** [January 4, 2021, 9:20am UTC](https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045/1 "2021-01-04T09:20:34Z")

</div>

I am trying to model a system that can operate in different modes. Each mode has some associated state of a particular type and this state can be updated or converted to a state value of another mode. I want to represent each mode as a module which contains the update and convert functions.

In Haskell, I might model this using an existential type:

```haskell
{-# LANGUAGE ExistentialQuantification #-}
data Mode s = forall n. Mode { next :: Mode n, step :: s -> s, advance :: s -> n }

```

My first attempt in OCaml was to represent `Mode` as a module type:

```auto
module type MODE = sig
    module Next: MODE

    type state
    val step: state -> state
    val advance: state -> Next.state
end

```

However, this causes an error because the declaration of `MODE` is not available while it is being defined.

I also attempted the trick of using a recursive outer module which is assigned to itself:

```auto
module rec ModeOuter: sig
  module type MODE = sig
    module Next: ModeOuter.MODE

    type state
    val step: state -> state
    val advance: state -> Next.state
  end
end = ModeOuter

```

However, this gives me an error as well:

```nohighlight
File "./main.ml", line 3, characters 17-31:
3 | module Next: ModeOuter.MODE
                     ^^^^^^^^^^^^^^
Error: Illegal recursive module reference

```

I am not exactly sure why OCaml considers this module reference illegal. Is there any other way to work around this?

Thanks for any help.

---

<div class="post-metadata">

**Author:** ![CraigFe](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/craigfe/32/1989_2.png) [@CraigFe](https://discuss.ocaml.org/u/CraigFe)\
**Post date:** [January 4, 2021, 9:52am UTC](https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045/2 "2021-01-04T09:52:09Z")

</div>

Hi @davidw,

This doesn’t really answer your question, but note that it’s possible write your Haskell example directly in OCaml with GADTs:

```ocaml
type 's mode = Mode : { next : 'n mode; step : 's -> 's; advance : 's -> 'n } -> 's mode

```

My instinct would have been to go in that direction rather than via recursive modules, mostly because I’ve found the latter to contain unpleasant pitfalls like the one you ran across.

I’m interested to know if there’s a solution there though; here’s hoping someone more knowledgeable than I comes along 🙂

---

<div class="post-metadata">

**Author:** ![octachron](https://avatars.discourse-cdn.com/v4/letter/o/49beb7/32.png) [@octachron](https://discuss.ocaml.org/u/octachron)\
**Post date:** [January 4, 2021, 12:27pm UTC](https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045/3 "2021-01-04T12:27:34Z")

</div>

It is possible to use first-class modules to bypass the restriction on recursive references:

```ocaml
module rec ModeOuter: sig
  module type MODE = sig
    type state
    type next_state
    val step: state -> state
    val advance: state -> next_state
    val next: unit -> next_state ModeOuter.mode
  end
  type 'a mode = (module MODE with type state = 'a)
end = ModeOuter

```

which behaves “as expected”:

```ocaml
open ModeOuter
module rec Integer: MODE with type state = int =
struct
  type state = int
  type next_state = string
  let step x = 1 + x
  let advance x = string_of_int x
  let next () = ((module String): next_state mode)
end
and String: MODE with type state = string =
struct
  type state = string
  type next_state = int
  let step x = x ^ x
  let advance x = int_of_string x
  let next () = ((module Integer): next_state mode)
end

```

---

<div class="post-metadata">

**Author:** ![yawaramin](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yawaramin/32/3384_2.png) [@yawaramin](https://discuss.ocaml.org/u/yawaramin)\
**Post date:** [January 6, 2021, 4:15pm UTC](https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045/4 "2021-01-06T16:15:16Z")

</div>

I wonder if OCaml could support `module type rec`. Seems logical given that types are recursive.

---

<div class="post-metadata">

**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\
**Post date:** [January 7, 2021, 8:28am UTC](https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045/5 "2021-01-07T08:28:39Z")

</div>

Yes, I would also use a direct translation with an existential type, rather than a module-level solution.

---

<div class="post-metadata">

**Author:** ![yallop](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yallop/32/517_2.png) [@yallop](https://discuss.ocaml.org/u/yallop)\
**Post date:** [January 7, 2021, 10:07am UTC](https://discuss.ocaml.org/t/is-there-any-way-to-write-recursive-module-types/7045/6 "2021-01-07T10:07:11Z")

</div>

> [@yawaramin](#):
>
> I wonder if OCaml could support `module type rec` . Seems logical given that types are recursive.

There’s an issue open here: [Recursive signatures · Issue #6818 · ocaml/ocaml · GitHub](https://github.com/ocaml/ocaml/issues/6818)