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?

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.

Answer 2

Use and

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