# Why are mutually recursive type aliases with lists are cyclic?

**URL:** <https://discuss.ocaml.org/t/why-are-mutually-recursive-type-aliases-with-lists-are-cyclic/15825>\
**Category:** Learning\
**Tags:** types\
**Created:** [December 20, 2024, 11:22pm UTC](https://discuss.ocaml.org/t/why-are-mutually-recursive-type-aliases-with-lists-are-cyclic/15825 "2024-12-20T23:22:21Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![flip-rossi](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/flip-rossi/32/4496_2.png) [@flip-rossi](https://discuss.ocaml.org/u/flip-rossi)\
**Post date:** [December 20, 2024, 11:22pm UTC](https://discuss.ocaml.org/t/why-are-mutually-recursive-type-aliases-with-lists-are-cyclic/15825/1 "2024-12-20T23:22:21Z")

</div>

I’m trying to define two mutually recursive types like this;

```ocaml
type transition = symbol * state
and state =
  | Nil
  | Cons of transition * state

```

which works fine, but then it leaves me wondering: Isn’t this logically the same as

```ocaml
type transition = symbol * state
and state = transition list

```

?

Why does the second case gets compiler error

```auto
The type abbreviation transition is cyclic:
         transition = symbol * state,
         symbol * state contains state,
         state = transition list,
         transition list contains transition

```

but the first one doesn’t?

---

<div class="post-metadata">

**Author:** ![Chet\_Murthy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chet_murthy/32/1501_2.png) [@Chet\_Murthy](https://discuss.ocaml.org/u/Chet_Murthy)\
**Post date:** [December 21, 2024, 2:12am UTC](https://discuss.ocaml.org/t/why-are-mutually-recursive-type-aliases-with-lists-are-cyclic/15825/2 "2024-12-21T02:12:37Z")

</div>

I sure am not a type theorist, nor an expert in the OCaml type inference algorithm, but in the second case you have two type abbreviations (though if you expand `state` it looks like constructors and not an infinite recursion, sure sure) whereas in the first, you have manifestly that `state` is a constructor data-type. Maybe it’s as simple as that. You can’t provide a collection of type-abbreviations that are mutually-recursive, full stop.

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [December 21, 2024, 9:03am UTC](https://discuss.ocaml.org/t/why-are-mutually-recursive-type-aliases-with-lists-are-cyclic/15825/3 "2024-12-21T09:03:59Z")

</div>

By default, the OCaml compiler rejects recursive types. You can enable them by passing option `-rectypes`. The downside is that error messages might become much less readable, since the compiler can now infer recursive types, which tend to hide the root location of bugs.

---

<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:** [December 21, 2024, 1:11pm UTC](https://discuss.ocaml.org/t/why-are-mutually-recursive-type-aliases-with-lists-are-cyclic/15825/4 "2024-12-21T13:11:38Z")

</div>

In your first example, you are defining a new nominal type:

```ocaml
type transition = symbol * state
and state =
  | Nil
  | Cons of transition * state

```

In particular, if we expand the first type abbreviation, we get

```ocaml
type state =
  | Nil
  | Cons of (symbol * state) * state

```

And thus this is an usual definition of a recursive nominal type, where the recursion is guarded behind the constructors (aka iso-recursion). In other words, the type of `Nil` or  
`Cons (('a', Nil), Nil)` is just `state`.

Contrarily, your second example only contains abbreviations for type expressions:

```ocaml
type transition = symbol * state
and state = transition list

```

and the recursive type expression appears clearly if we expand the first abbreviation:

```ocaml
type state = (symbol * state) list

```

Here it is the type expression which is recursive (aka equi-recursion): the type of  
`[('a', [])]` seen as a `state` would be `(symbol * 'state) list as 'state`. This is only allowed with `-rectypes` or when the recursion goes through a polymorphic variants or objects:

```ocaml
type state = [`Cons of symbol * state | `Nil]

```

Moreover, beware that this definition of an automaton only works if the automaton digraph is acyclic, or if you define it whole-piece in a recursive value definition (which doesn’t scale well).