# Fixed point transformers

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?

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?