# Recursive Types In Ocaml

A question came up at lunch today that was kind of interesting: in a strongly-typed language, what is the type of a function that takes a list of functions like itself?

Of course, such a thing is easy to write in Python, since everything is dynamic:

``````def p0(aList):
print "p0"
if aList:
(aList[0])(aList[1:])

def p1(aList):
print "p1"
if aList:
(aList[0])(aList[1:])

p0([p0,p1,p0,p1])
``````

But what about with a strongly-typed language like Ocaml? An obvious first attempt won’t work:

``````# type t = t list -> unit;;
Characters 4-23:
type t = t list -> unit;;
^^^^^^^^^^^^^^^^^^^
The type abbreviation t is cyclic
``````

… so one is maybe left with the conclusion that it is impossible to express such a thing with strict type-checking. However, it turns out that it is not only possible, it is easy! The trick is that recursive types must go through an object, so with a quick modification…

``````type t = Y of (t list -> unit)

let p0 aList =
print_string "a0";
match aList with
| Y fn::rest -> fn rest
| _ -> ()

let p1 aList =
print_string "a1";
match aList with
| Y fn::rest -> fn rest
| _ -> ()

p0 [Y p0; Y p1; Y p0]
``````

It’s amazing that it’s not much longer than the Python version, yet is still fully typechecked. Take a look at this message by Xavier Leroy for some details on recursive types and their implementation in Ocaml.

Bonus: If you run with the -rectypes option of Ocaml, you can even skip going through an intermediate object; you can just write out the method, and Ocaml’s automagical-type induction works perfectly:

``````# let p0 aList =
print_string "a0";
match aList with
| fn::rest -> fn rest
| _ -> ();;
val p0 : ('a list -> unit as 'a) list -> unit =

# p0 [p0];;
p0p0
``````

## Discussion

Comments are moderated whenever I remember that I have a blog.