Fixed point transformers


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

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

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
  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:(cata f) |> f
    let transform_bottom_up f x = cata (Fn.compose f fix) x

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

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