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)(aList[1:]) def p1(aList): print "p1" if aList: (aList)(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
Comments are moderated whenever I remember that I have a blog.
There are no comments on this article.