Instance modules for more-parametrized-types

Learning
1

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

7 Likes
2

Thank you very much for starting this conversation. This is indeed a question that arises, probably, in anyone who has ever read Haskell. My first approach to managing two-parameters type-constructors was to… simply avoid it by fixing one of the two types. For example instead of having ('a, 'b) result I use ('a, exn) result. It’s a little bit like putting the dust under the carpet and it doesn’t answer your question at all, but in a lot of cases, it was enough for me.

In order to implement ('a, 'b) Either.t as “higher-kinded functional abstractions (functors, applicatives, monads)”, we have experimented some approach.

The first used an approach that looked like this (the code is writen during the redaction of the message, so it is possible that it do not compile and I’ll pass some implementation details):

We use a FUNCTOR2 (or more) as “base”:

module type FUNCTOR2 = sig 
   type ('a, 'b) t
  val map : ('b -> 'c) -> ('a, 'b) t -> ('a, 'c) t
end

Now, we can have an implementation for Either

module Either = Functor2.Make (struct
    type ('a, 'b) t = Left of 'a | Right of 'b
    let map f = function 
      | Left x -> Left x 
      | Right x -> Right (f x)
end)

We define FUNCTOR (as an 1-parameter type-constructor) :

module type FUNCTOR = sig 
   type 'a  t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

And we use FUNCTOR2 to define FUNCTOR:

module Functor = struct
    module Make (F: FUNCTOR) = Functor2.Make (struct
      type (_, 'a) t = 'a F.t
      include (F : FUNCTOR with type 'a t := 'a F.t)
    end)
end

This approach looks nice (DRY), but we face to some problems. We have to add, at the user-level, somme type equalities and it was not very conveinent… So we decide to drop it.

After reading the proposal of @gasche, I was a little bit wary. I feel that the proposal was a step forward, but (my bad), I thought the proposal, although flexible, was a bit hard to read (and to use). So we use, in the case of Either.t, an other representation:

We define 1-parameter type constructor for Functor, Applicative and Monad, here’s the example with (only) Functor:

module type FUNCTOR = sig 
   type 'a  t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

And we provide an intermediate Functor (Ă  la ML) to let the user chosing the left type of Either :

module Either = struct 

   type ('a, 'b) t =
     | Left of 'a
     | Right of 'b

   module Functor (T : sig type t end) = 
       Functor.Make (struct
         type nonrec 'a t = (T.t, 'a) t
         let map f = function 
            | Left x -> Left x 
            | Right x -> Right (f x)
       end)
end

So the user can pass a t when he want to specialize Either, to use it as a simple Functor. (Thanks to local module-opening, we have a conveinent syntax to open locally "specialized Either). But with this approach, it is impossible to change the type of Left (in bind in the case of Monad, for example). So to be able to change the Left type, we introduce a new abstraction in the body of Either a bifunctor :

module Either = struct 

   type ('a, 'b) t =
     | Left of 'a
     | Right of 'b

   module Bifunctor = Bifunctor.Make (struct
       type nonrec ('a, 'b) t = ('a, 'b) t
       let bimap f g = function
           | Left x -> Left (f x) 
           | Right x -> Right (g x)
   end)

   module Functor (T : sig type t end) = 
       Functor.Make (struct
         type nonrec 'a t = (T.t, 'a) t
         let map f = (* we can rewrite map using bimap *)
            Bifunctor.bimap (fun x -> x) f x
       end)
end

Exposing a Bifunctor in Either allow us to switch the type of the left part of Either, (using Bifunctor.first/second or bimap) and we can keep the combinators of Functor, Applicative and Monad with 1 type parameter.

I like this approach because, in the specific case of Either (and possibly Pair) I find that it allows easy re-use of what has already been designed, while not restricting the use of the two parameters of types of Either. And I find it easier to read (but it is a personal opinion).

By the way, the two approach are very close… FunctorPair from @gasche proposal share properties with Bifunctor (the two parameters are both covariant functors) and, in the case of Either… I was Lucky…

But, the proposal of @gasche takes advantage of the curryfication of Functors, and composition between abstraction (ie, the example of map) are more powerful. So I’ll investigate “how to use them” and “how to organize my files” to take advantage of the initial proposal.

Here was the method I involve in order to have “multi parameters abstraction”.

I’d love to hear from you, and thank you for initiating this conversation!

P.

1 Like