Mutually recursive types in OCaml

Question

In Haskell you can do the following:

Prelude> data Foo = Foo Bar; data Bar = Bar Foo

How can you do the same thing in OCaml? I tried:

                    ___
# type foo = Foo of bar;; type bar = Bar of foo;;
Error: Unbound type constructor bar

Is it even possible to define mutually recursive data types in OCaml? If not then why?

Comparing data definitions to let expressions: mutually recursive data types correspond to using let rec (or more appropriately type rec for want of a better phrase). What are the advantages of being able to define mutually recursive data types? My foobar example is trivial. Can you think of any non-trivial uses of mutually recursive data types?

Photovoltaic

Answer 1

ivg answered your question, but here's a non-trivial mutually recursive type.

module Stream = struct

  type 'a t    = unit -> 'a node
   and 'a node = Nil
               | Cons of 'a * 'a t 

end

This is the genuine type of spine-lazy streams. That said, you could construct it without mutually recursive types

type 'a t = Stream of (unit -> ('a * 'a t) option)

Offhand my thought is that you can always reduce a family of mutually recursive types into a single one if you like (though perhaps not in OCaml—the encoding I'm thinking of would make non-trivial use of dependent type indices), but it can certainly be more clear directly.

Rockery

actually, your second type definition doesn't work, it will say that type definition is cyclic. The correct way would be type 'a t = Stream of (unit -> ('a * 'a t) option) – Earthward

Oh, whoops! Yep, didn't check it in the interpreter. Fixed now, thanks. – Rockery

Answer 2

Use and

type foo = Foo of bar
 and bar = Bar of foo

Earthward

Explicit mutual recursion. I like that more than the Haskell syntax. Explicit is always better than implicit. – Photovoltaic

It's actually annoyingly slightly less than totally explicit. What would be maximally explicit would be type rec foo = Foo of bar and bar = Bar of foo. You run into (small) issues when, for instance, there's an ambient type t and you'd like to make a new type t in a submodule which aliases the ambient t, but type t module X = struct type t = t end is an error because it assumes you mean to construct the infinite type type x = x. – Rockery

there is an interesting several years discussion on this topic, that results in a new nonrec keyword. In 4.03 we will have type nonrec t and even (I'm not sure whether it ended up in the final patch) type rec t. – Earthward

So type rec is still the default? You can just add the declaration to be extra explicit? – Rockery