Fixed point transformers

Learning
1

Hi,

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?

2

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?