However in Ocaml at least you cannot actually write a single
definition for map in terms of a single fold -- you have to
write out fold for each data type, and worse, even given that
you still need to write out map for each data type too,
following an idiomatic pattern.

How could Ocaml be extended to get rid of this unsafe
verbosity?

Even if the resulting generic operators weren't first class,
it would still be useful to define 'map' once and be done
with it.