Types of Widen at ocaml

Question

I am trying to write a free monad library in ocaml following the haskell Control.Monad.Free , but I was stuck at some point in the implementation of hoistFree.

hoistFree :: Functor g => (forall a. fa -> ga) -> Free fb -> Free gb hoistFree _ (Pure a) = Pure a hoistFree f (Free as) = Free (hoistFree f <$> f as) 

Here is my translation attempt.

 let rec hoistfree : 'b.('bt -> 'bt) -> 'am -> 'am = fun fx -> match x with | Return x -> Return x | Free x -> Free (T.map (hoistfree f) (fx));; 

Unfortunately, I get a message stating that I am not decrypting type g correctly.

 Error: This definition has type ('bmt -> 'bmt) -> 'bm -> 'bm which is less general than 'a. ('at -> 'at) -> 'bm -> 'bm 

Everything works fine if I don't insert a function type annotation, but then, as the error message says, I don't get the generic type for f. What is the problem? How can I extend type f?

Answer 1

I am not very familiar with Ocaml, but I believe that

 let rec hoistfree : 'b.('bt -> 'bt) -> 'am -> 'am = 

analyzed as

 let rec hoistfree : 'b. ( ('bt -> 'bt) -> 'am -> 'am ) = 

instead

 let rec hoistfree : ('b. ('bt -> 'bt)) -> 'am -> 'am = 

The former is the main polymorphic type, the latter is the rank2 type, which requires more support from the type system than the Hindley-Milner.

IIRC, to achieve the latter, you need to determine the data type of the custom wrapper. For instance:

 type poly = { polyf: 'a . 'a -> 'a } ;; let foo (x: poly): int = x.polyf 4;; let bar: poly = { polyf = fun x -> x } ;; let _ = print_string ("hello " ^ string_of_int (foo bar));;