Widen typy w ocaml

Question

Próbuję napisać bezpłatną bibliotekę monad w ocaml, po Control.Monad.Free z haskell, ale utknąłem w pewnym momencie, w realizacji hoistFree.

hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b 
hoistFree _ (Pure a) = Pure a 
hoistFree f (Free as) = Free (hoistFree f <$> f as) 

Oto moja próba tłumaczenia.

let rec hoistfree : 'b.('b t -> 'b t) -> 'a m -> 'a m = 
     fun f x -> match x with 
     | Return x -> Return x 
     | Free x -> Free (T.map (hoistfree f) (f x));; 

Niestety pojawia się błąd informujący, że nie poszerzam prawidłowo typu g.

Error: This definition has type ('b m t -> 'b m t) -> 'b m -> 'b m 
     which is less general than 'a. ('a t -> 'a t) -> 'b m -> 'b m 

Wszystko działa dobrze, jeśli nie wstawić typ funkcja adnotacji, ale jak mówi komunikat o błędzie, nie rozumiem ogólny typ dla F. Gdzie jest problem? Jak mogę rozszerzyć typ f?

Answer 1

nie jestem bardzo obeznany z SML ale wierzę, że

let rec hoistfree : 'b.('b t -> 'b t) -> 'a m -> 'a m = 

jest analizowany jako

let rec hoistfree : 'b. (('b t -> 'b t) -> 'a m -> 'a m) = 

zamiast

let rec hoistfree : ('b. ('b t -> 'b t)) -> 'a m -> 'a m = 

Były to podstawowy rodzaj polimorficzny, ten drugi to typ rank2, który wymaga więcej wsparcia ze strony systemu typu niż Hindley-Milner.

IIRC, w celu osiągnięcia tego ostatniego należy zdefiniować niestandardowy typ danych opakowania. Na przykład:

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));;