Instance modules for more-parametrized-types

There are nice higher-kinded functional abstractions (functors, applicatives, monads) that characterize the structure of one-parameter type functions, that naturally map in OCaml to one-parameter parametrized types.

(* abstraction *)
module type Functor = sig
  type 'a t
  val fmap : ('a -> 'b) -> 'a t -> 'b t
end

(* instance for lists *)
module FunctorList : Functor with type 'a t = 'a list =
  ...

Unfortunately, there is an impedance mismatch when we want to define instances for types that have more than one parameter. How should we say, for example, that ('a, 'b) result is a functor in its first parameter, or in both its parameters?

I must say that this a design question where I’m not personally satisfied with the solutions that OCaml offers currently. I have played with various approaches to this problem and (even independently from the relative verbosity of the functor syntax) they all feel cumbersome when used at scale. (Notably I worked on it with @c-cube years ago in the context of a stalled PR for the Batteries library, batteries#501). My personal (non)solution is to reduce the use of those generic abstractions to a minimum in my code (I use monadic/applicative operators but, generally, few operations abstracted on any monad/applicative): if it hurts, don’t do that. But this is inconvenient in some problem domains which use them heavily.

(I think that the “modular implicit” work could improve things quite a bit, in a distant future when it makes progress.)

In a discussion with @xvw I proposed the following approaches. Instead of defining, say, an “functor with an extra parameter”, I stick to manipulating one-parameter abstractions, and use currification (at the functor level) to abstract over the other parameters.

module FunctorInstancesAsModules : sig end = struct
  (* generic stuff *)
  module type Functor = sig
    type 'a t
    val fmap : ('a -> 'b) -> 'a t -> 'b t
  end

  module FunctorList = struct
    type 'a t = 'a list
    let fmap = List.map
  end

  module FunctorPair (F : Functor) (G : Functor) = struct
    type 'a t = 'a F.t * 'a G.t
    let fmap f (u, v) = (F.fmap f u, G.fmap f v)
  end

  (* For parametrized types, we use functors for currification *)
  module type Ty = sig
    type t
  end

  let result_fmap2 ok err = function
    | Ok v -> Ok (ok v)
    | Error v -> Error (err v)

  module FunctorResult1 (X : Ty) = struct
    type 'a t = ('a, X.t) result
    let fmap f = result_fmap2 f Fun.id
  end

  module FunctorResult2 (X : Ty) = struct
    type 'a t = (X.t, 'a) result
    let fmap g = result_fmap2 Fun.id g
  end

  (* Example use-case *)
  type 'a foo = 'a list * ('a, exn) result
  let weird_map (type a b) : (a -> b) -> a foo -> b foo =
    let module F = FunctorPair(FunctorList)(FunctorResult1(struct type t = exn end)) in
    F.fmap
end
module FunctorCombinators : sig end = struct
  (* generic stuff *)
  module type Functor = sig
    type 'a t
    val fmap : ('a -> 'b) -> 'a t -> 'b t
  end

  module FId = struct
    type 'a t = 'a
    let fmap f x = f x
  end

  module type Ty = sig
    type t
  end
  module FConst (X : Ty) = struct
    type _ t = X.t
    let fmap _f x = x
  end

  module FList (F : Functor) = struct
    type 'a t = 'a F.t list
    let fmap f = List.map (F.fmap f)
  end

  module FPair (F : Functor) (G : Functor) = struct
    type 'a t = 'a F.t * 'a G.t
    let fmap f (u, v) = (F.fmap f u, G.fmap f v)
  end

  (* result is a (covariant) functor in both its argument *)
  module FResult (F : Functor) (G : Functor) = struct
    type 'a t = ('a F.t, 'a G.t) result
    let fmap f = function
      | Ok v -> Ok (F.fmap f v)
      | Error v -> Error (G.fmap f v)
  end

  (* example use-case *)
  type 'a foo = 'a list * ('a, exn) result
  let weird_map (type a b) : (a -> b) -> a foo -> b foo =
    let module F =
      FPair
        (FList(FId))
        (FResult(FId)(FConst(struct type t = exn end)))
    in
    F.fmap
end

I’m opening this topic so that people can suggest better solutions if they have some, or maybe point to their monad/applicative-generic library / code organization.

Note: Haskell has curried type parameters, which somewhat improve on this situation, but it is far from a complete solution for this problem. For the example of ('a, 'b) result, that is Result a b, it is easy to talk about Result a, and so define a Functor instance on it, but talking about (\a -> Result a b) (which is the one you want in practice) is still very cumbersome.

And then there are generic-programming approaches where, instead of one-parametrized functors, one works with bifunctors or dinatural transformations. I’m skeptical that we can get a usable, accessible encoding of these ideas in library form today. (They require exporting a rich “parameter space” at the type level, which is too advanced for my taste of using simple abstractions. Unless one is working in a fully-dependent language where they are easier than in OCaml/Haskell and where everything else is more difficult, so it evens out.)

5 Likes