Is there any way to write recursive module types?

Learning
, ,
#1

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:

{-# 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:

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:

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:

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.

1 Like
#2

Hi @davidw,

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

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 :slight_smile:

2 Likes
#3

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

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”:

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
2 Likes
#4

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

#5

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

#6

There’s an issue open here: Recursive signatures · Issue #6818 · ocaml/ocaml · GitHub

1 Like