Instance modules for more-parametrized-types

Learning
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