# brool

brool \brool\ (n.) : a low roar; a deep murmur or humming

# 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 = <fun>

# p0 [p0];;
p0p0```