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.

There are no comments on this article.