I’ve been trying to figure out how to express some Haskell code which makes use of higher kinded types in terms of OCaml functors. The types of interest are:

type Fix f = Fx (f (Fix f))
type TFix
(t :: (* -> *) -> (* -> *))
(f :: ((* -> *) -> (* -> *)) -> * -> *) =
Fix (t (f t))

The first, the fixed point of some type 'a t is straightforward:

module Fix(F: sig type 'a t end) = struct
type t = Fx of t F.t
end

The second type, which gives the fixed point of f parameterized by a ‘transformer’ t, would seem to need a higher order OCaml functor i.e. a functor which accepted a functor as an argument.

For context, the Haskell code is used to solve the AST typing problem and uses the following ‘annotation transformer’ to get a fixed point of some type with annotations:

type AnnotT a f r = AnnF (f r , a)
type AnnotTFix a f = TFix (AnnotT a) f

Is this possible and/or is there a better way to express this in OCaml?

Ah! I think writing that down made it click! I now have the following:

module Functor = struct
module type S = sig
type 'a t
val map : 'a t -> f:('a -> 'b) -> 'b t
end
end
module Fix = struct
module type S = sig
module F : Functor.S
type t
val fix : t F.t -> t
val unfix : t -> t F.t
val cata : ('a F.t -> 'a) -> t -> 'a
val transform_bottom_up : (t -> t) -> t -> t
end
module Make(F:Functor.S) : S with module F := F = struct
type t = Fx of t F.t
let fix x = Fx x
let unfix (Fx x) = x
let rec cata f x = unfix x |> F.map ~f:(cata f) |> f
let transform_bottom_up f x = cata (Fn.compose f fix) x
end
end
module TFix = struct
module type S = sig
module T : functor (F : Functor.S) -> Functor.S
module F : functor (T : functor (F : Functor.S) -> Functor.S) -> Functor.S
include Fix.S with module F := T(F(T))
end
module Make
(T : functor (F: Functor.S) -> Functor.S)
(F: functor (T : functor (F: Functor.S) -> Functor.S) -> Functor.S) = Fix.Make(T(F(T)))
end

My question remains, is there a better way to do this in OCaml?