5

我正在尝试在 ocaml 中编写一个免费的 monad 库，遵循来自 haskell 的Control.Monad.Free，但我在一个点上卡住了，在葫芦 Free 的实现中。

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)

这是我的翻译尝试。

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

不幸的是，我收到一个错误，告诉我我没有正确扩大 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

如果我不插入函数类型注释，一切正常，但是正如错误消息所说，我没有得到 f 的一般类型。问题出在哪里？如何扩大 f 的类型？

4

1 回答 1

3

我对 Ocaml 不是很熟悉，但我相信

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

被解析为

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

代替

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

前者是基本的多态类型，后者是 rank2 类型，它比 Hindley-Milner 需要更多类型系统的支持。

IIRC，要实现后者，您需要定义自定义包装器数据类型。例如：

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));;
于 2016-09-10T19:16:53.537 回答