What's the use of this mutually recursive type definition in OCaml? - Stack Overflow

Below is a valid variant type definition in OCaml. (source)

type t = U of u and u = T of t

Is there a use for it?

And how to create a value of type t? Or type u?

Below is a valid variant type definition in OCaml. (source)

type t = U of u and u = T of t

Is there a use for it?

And how to create a value of type t? Or type u?

• ocaml

Share Improve this question Follow edited Feb 2 at 4:17 smwikipedia asked Feb 1 at 12:19 smwikipediasmwikipedia 64.5k9898 gold badges331331 silver badges507507 bronze badges 1

• 1 You can create cyclic values of both types at once: let rec t = T u and u = U t;; – Naïm Favier Commented Feb 1 at 14:24

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 4

The example you've shown does not make much sense. There's no way for the recursion to end.

As Naïm Favier notes, you can actually create a value, but the cyclic nature of the values will be noted by OCaml.

# let rec t = T u and u = U t;;
val t : u = T (U <cycle>)
val u : t = U (T <cycle>)

But with that, mutually recursive types can be very useful. Consider the definition of Seq.t from the standard library.

type 'a t = unit -> 'a node
(** A sequence [xs] of type ['a t] is a delayed list of elements of
    type ['a]. Such a sequence is queried by performing a function
    application [xs()]. This function application returns a node,
    allowing the caller to determine whether the sequence is empty
    or nonempty, and in the latter case, to obtain its head and tail. *)

and +'a node =
  | Nil
  | Cons of 'a * 'a t (**)
(** A node is either [Nil], which means that the sequence is empty,
    or [Cons (x, xs)], which means that [x] is the first element
    of the sequence and that [xs] is the remainder of the sequence. *)

Source