[Drup]

Well, multisets, multimaps and a lot of other things are also provided in containers and core. It's nice that you (already!) adopted that style of iterator.

I'm not sure what an "OCaml compatibility layer" would mean. It's already OCaml-y: it's referentially transparent and full of functors and signatures! The main weird thing is that the type of compare is not the same (I understand why, but I find compatibility more valuable). The naming convention matters little, as long as it's clear, readable and consistent (OCamlers are not going to boycott a library because it uses camlCase).

I don't think the signature indirection is a real problem, you just need a good tool for documentation generation that inlines signatures. You can ask the odoc people, I'm sure they would be happy to help you. I'm surprised there is no "reasondoc" tool just yet. :)