The n-ary cartesian product (on lists) returns the cartesian product of a list of list, rather than just two lists:
product [; [2;3]; [4;5]] is
[[1;2;4]; [1;2;5]; [1;3;4]; [1;3;5]]. The result is the empty list as soon of one of the input lists is empty. But what is the product of the empty list of lists?
I first answered this question with mathematical considerations that, while working on set theory, will fell familiar to anyone having worked with dependent types. But there is a direct, much simpler answer in the code.
During the second part of my internship this summer, I worked on a test implementation for a new data structure in OCaml : Hash Array Mapped Tries (HAMT). I did not have the time to finish it, but I now have a usable and quite complete version, still to be more documented but already available at http://gitorious.org/ocaml-hamt.
On this article, I will quickly explain the principles and the use cases of this structure, and I will expose a few details of my implementation in OCaml.