Type substitution inside a functor


I’m requiring your help in order to write a functor signature. Sometimes in the code, we end up with types nested in several levels. For example 'a Lwt.t option Lwt.t.

I’m trying to build a binding operator to simplify things a bit, which leads me to build a function with the following signature:

'a option Lwt.t -> ('a -> 'b Lwt.t) -> 'b option Lwt.t

Following the types, I can get this implementation:

let f : 'a option Lwt.t -> ('a -> 'b Lwt.t) -> 'b option Lwt.t =
 fun v f ->
  Lwt.bind v (function
    | Some x -> Lwt.map (fun x -> Some x) (f x)
    | None -> Lwt.return_none)

Actually, this function could be generalized with any other monadic type. I just need to have bind, map and return:

module type Monadic = sig
  type 'a t

  val map : ('a -> 'b) -> 'a t -> 'b t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t

module WrappableOption (T : Monadic) =
    type 'a t = 'a option

    let inject : 'a t T.t -> ('a -> 'b T.t) -> 'b t T.t =
     fun v f ->
      T.bind v (function
        | Some x -> T.map (fun x -> Some x) (f x)
        | None -> T.return None)

If I want to use this pattern with other types (as long as I can access to the contsructors — for example result), I have to write the signature for this functor. And I do not know how to express it. The generic signature would be:

module type Wrappable = functor (T : Monadic) -> sig
  type 'a t

  val inject : 'a t T.t -> ('a -> 'b T.t) -> 'b t T.t

but this signature make the type 'a t abstract. As a consequence this make the whole functor useless. I need a way to substitute the type inside the signature, but I do not know how to write it:

module WrappableOption : Wrappable with type 'a t = 'a option =
  (T : Monadic)

does not compile: (of course)

module WrappableOption : Wrappable with type 'a t = 'a option =
Error: This module type is not a signature

I do not use the functors a lot, and I really do not know how to do this. Of course I could rewrite the signature for each module, but I would like to know if there is a generic way for this ?

Thanks !

Just a quick note that the concept you are describing here is known as “traversable” and the inject function is known as “traverse”.

1 Like

Thanks! I didn’t know for that. I will search if I can find any solution with thoses keywords

module type Monad = sig
  type 'a t

  val return : 'a -> 'a t
  val bind : ('a -> 'b t) -> 'a t -> 'b t

module type Traversable = sig
  type 'a t

  module Make (M : Monad) : sig
    val traverse : ('a -> 'b M.t) -> 'a t -> 'b t M.t

module TraversableOption : Traversable with type 'a t = 'a option = struct
  type 'a t = 'a option

  module Make (M : Monad) = struct
    let traverse f = function
      | None -> M.return None
      | Some x -> f x |> M.bind @@ fun y -> M.return (Some y)

module Identity : Monad = struct
  type 'a t = 'a

  let return = Fun.id
  let bind = Fun.id

let x =
  let module T = TraversableOption.Make (Identity) in
  T.traverse (fun x -> Identity.return (x + 40)) (Some 2)

I should add that you usually only need an Applicative, rather than a Monad, to make traverse.


I see, you declare a functor inside the Traversable module (I was trying to create the Traversable module with the target type directly), this way you have all the required types available.

Thanks a lot, I would not be able to figure how to build that by myself, this is very helpfull!

1 Like