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