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.