Re-use Bifunctor newtypes where appropriate

[garyb]

For the next round of breaking-change releases.

See #22 (comment)

[hdgarrood]

@joneshf, @MonoidMusician and I were discussing on Slack and here's what we came up with.

@joneshf suggested making the following a superclass of both Bifunctor and Profunctor, in functors:

class Functor1 f where
  rmap :: forall a b c. (b -> c) -> f a b -> f a c

We could then define all of the following in functors:

• newtype Clown f a b = Clown (f a)
• newtype Joker f a b = Joker (f b)
• newtype Wrap f a b = Wrap (f a b), with the instance Functor1 f => Functor (Wrap f a)
• newtype Flip f a b = Flip (f b a)
• newtype Product2 f g a b = Product2 (f a b) (g a b), so as not to overlap with the Product which is already in functors
• newtype Star f a b = Star (a -> f b)
• newtype Costar f b a = Costar (f b -> a)
• newtype Split f a b = Split (exists x. Tuple3 (a -> x) (x -> b) (f x))

All of these can have Functor1 instances, and additionally, we would define the following instances in bifunctors or profunctors as appropriate, in the same module as the class:

• Functor f => Bifunctor (Clown f)
• Contravariant f => Profunctor (Clown f)
• Functor f => Bifunctor (Joker f)
• Functor f => Profunctor (Joker f)
• Bifunctor f => Bifunctor (Wrap f)
• Profunctor f => Profunctor (Wrap f)
• Bifunctor f => Bifunctor (Flip f)
• no Profunctor (Flip f), as it's not possible without some "flipped profunctor" class
• Bifunctor f, Bifunctor g => Bifunctor (Product2 f g)
• Profunctor f, Profunctor g => Profunctor (Product2 f g)
• no Bifunctor (Star f), as it's not possible
• Functor f => Profunctor (Star f)
• Contravariant f => Bifunctor (Costar f)
• Functor f => Profunctor (Costar f)
• no Bifunctor (Split f), as it's not possible
• Profunctor (Split f)

The only potentially difficult instance is Profunctor f => Contravariant (Flip f a), as it needs to be in the same module as either Contravariant or Flip but it also needs to have Profunctor in scope. Maybe we can just accept defeat on that one and let Cowrap continue to exist in profunctors.

A nice bonus of this is that there is no longer any need to have two separate rmap functions.

[garyb]

Functor1 seems a little odd to me, I spent quite a while thinking about it, and finally realised why: rmap isn't really even something that needs to exist - it should always just be map. This is a case where quantified constraints would be great:

class (forall x. Functor (f x)) <= Bifunctor f where
  bimap :: forall a b c d. (a -> b) -> (c -> d) -> f a c -> f b d
  lmap :: forall a b c. (a -> b) -> f a c -> f b c

class (forall x. Functor (f x)) <= Profunctor f where
  dimap :: forall a b c d. (a -> b) -> (c -> d) -> f b c -> f a d
  lcmap :: forall a b c. (a -> b) -> f b c -> f a c

[hdgarrood]

Right, but I think, even if we had quantified constraints, it can still be useful sometimes to draw attention to the fact that you're mapping over the right-hand type variable in a type of kind Type -> Type -> Type (as opposed to just any Functor), so I think I would still appreciate the existence of an rmap. Also, I think the hierarchy is probably easier to grok with the formulation involving rmap.

[masaeedu]

@hdgarrood Can Clown really have a Functor1 instance?

EDIT: yes it can, b is phantom :)

[garyb]

Not really important, but I think the Functor1 here is more like FunctorR or something, since

class Functor1 t where
  map1 ∷ ∀ f g. (f ~> g) → t f → t g

[JordanMartinez]

Looking over this issue, so the final class name should be FunctorR then rather than Functor1?

[kl0tl]

Given purescript/purescript-bifunctors#17, should we rather name it FunctorRight (or rename ApplyLeft, ApplicativeLeft, BindLeft and MonadLeft to ApplyL, ApplicativeL, BindL and MonadL)?

[hdgarrood]

Using full words rather than abbreviations here sounds good to me.

[JordanMartinez]

I'll get started on this.

[JordanMartinez]

Flip can't be defined in functors because it's Functor instance depends on the p having a Bifunctor instance:

instance functorFlip :: Bifunctor p => Functor (Flip p a) where
  map f (Flip a) = Flip (lmap f a)

[JordanMartinez]

First PR here: purescript/purescript-functors#27

[rhendric]

Why move Flip, Star, and Split, if they can be bifunctors/profunctors but not both?

[JordanMartinez]

Just wanted to remind people here that this PR is ready for review: purescript/purescript-functors#27

[hdgarrood]

Why move Flip, Star, and Split, if they can be bifunctors/profunctors but not both?

Good point. I think moving only the types that can be both bifunctors and profunctors to functors sounds good; if Star and Split can stay put then that's less breaking.

[JordanMartinez]

I posted a summary of the problem here, but here's a graph showing the nuances (at least, to my knowledge). Is the "Desired Dependency Graph" correct?

[rhendric]

In the desired world, what will happen to Data.Functor.Product and Coproduct, which use tuples and either? Will they be moved to the tuples and either packages?

(For types that are this interrelated, I wonder if these package divisions are too fine-grained.)

[JordanMartinez]

Yeah... I'm wonderinng the same thing. Here's the module dependency graph between the above packages (current, not with FunctorRight type class):

[JordanMartinez]

Ah... I think I see what we were trying to do... FunctorRight was defined in functors when it should be defined in bifunctors. functors would add a dependency on profunctors. Then, we'd get something like this:

Which produces this package graph

[hdgarrood]

I find it a bit weird having functors depending on bifunctors and profunctor, I think having it the other way around (having both bifunctors and profunctor depend on functors) would make more sense to me. I guess that would probably require moving bifunctors and profunctor so that they depend on both either and tuples, and moving all of the bifoldable and bitraversable instances out of foldable-traversable and into bifunctors? Does that sound like it would work?

[JordanMartinez]

Does that sound like it would work?

It can. I'm producing a final graph that helps me understand the full changes we'll be making.

[garyb]

Maybe we could merge just functors, bifunctors, profunctors? Or is that too far? I'm more of a fan of granularity in core libraries than some I think, but it seems like maybe they don't need to all be separate in this case - they're all flavours of functor in the end.

[hdgarrood]

Merging those three libraries all sounds reasonable to me, yeah. Then I think the only rearranging that needs to happen is for the Bifoldable and Bitraversable instances for the Clown, Joker, etc types to move from foldable-traversable to this new functors library. (I think "functors" is probably still an appropriate name?)

[garyb]

Yeah 👍 merging into functors was what I had in mind.

But yes, true! Assuming the instances and whatnot all make sense too.

[JordanMartinez]

If we're going to go with that approach (merging these into one library), I'm assuming the package graph would look like this then?

If that's the case, then should we also throw contravariant into that merge, too? Or at the very least, move Data.Functor.Contravariant into the functors package? purescript-profunctor is the only package in this list that depends on purescript-contravariant. I'm not sure what else (if anything) depends on it.

[hdgarrood]

I am suggesting that the Bifoldable and Bitraversable classes stay in foldable-traversable. It’s just the instances for the data types which now live in functors (Clown, Joker, etc) that I’m suggesting move to functors.

[JordanMartinez]

For consistency I think I'm going to stick to that for the rest of the PRs?

Yeah, be consistent. We'll fix it in the release if it needs to be. Based on Harry's comment above, I don't think we'll make a change.

[srghma]

merged, awesome, now it's left to fix

  in module Data.Bifoldable
  at .spago/foldable-traversable/master/src/Data/Bifoldable.purs:16:1 - 16:38 (line 16, column 1 - line 16, column 38)

    Module Data.Bifunctor.Wrap was not found.
    Make sure the source file exists, and that it has been provided as an input to the compiler.

in foldable-traversable

and

.spago/halogen/hydration-wip-2/src/Halogen/Component.purs
22:import Data.Bifunctor.Wrap (Wrap(..))

in halogen

(that's all I have found in my local projects)

[rhendric]

We have a few more PRs to merge in the core libraries before it's time to start hunting down breaks elsewhere. After #41, there will be PRs for functors, then foldable-traversable, then parallel (which wasn't properly part of the refactoring but I think it's the only other core library to be affected).

[JordanMartinez]

Only one more to go.

[JordanMartinez]

I've opened purescript/package-sets#807 to determine what else was affected by these changes.

[JordanMartinez]

Ok, looks like everything works now. I believe we can close this issue.

Thanks @rhendric for all your work! Your approach was better than the one I proposed.

[srghma]

could someone tell where is the Data.Bifunctor.Wrap

I see

  - `Wrap` was deleted; it is expected that any instances of `Bifunctor` will be accompanied by a corresponding instance of `Functor` (#22)

but it's not there

  22  import Data.Functor.Wrap (Wrap(..))
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

  Module Data.Functor.Wrap was not found.
  Make sure the source file exists, and that it has been provided as an input to the compiler.

[garyb]

It says

Wrap was deleted

😄

It was there to provide a Functor instance for every Bifunctor, but every Bifunctor should already have a Functor instance, which is why it was removed.

[srghma]

@garyb aaaaaa, tnx!
phah

[hdgarrood]

I think deleting Wrap makes slightly less sense now that we discarded the plan of introducing FunctorRight, actually.. maybe we should reintroduce it after all. On reflection I think Wrap has a valid use case when you have a generic Bifunctor and you want to use it with some function which has a Functor constraint.

[garyb]

My preferred solution for this is the thing I posted way back at the start of this thread: #23 (comment)

But since that isn't possible right now, I like the Wrap solution better than FunctorRight personally.

[hdgarrood]

Yeah, agreed, it'd be nice to have quantified constraints but in the meantime Wrap is probably best.

[hdgarrood]

(sorry!)

[rhendric]

In principle I halfway agree with you? There's a part of me that wants to advance the position that every class should have a newtype associated with it, for those times when you want to say that any instance of class X can be used as a class Y but you don't want to create a universal instance. It's a useful trick for dealing with the limitations of classes and instances, and maybe it should be more widely adopted.

But on the other hand, look at this commit @srghma just linked. Getting rid of Wrap forced that code to be better. I'd be willing to bet that this will be the case in most of the places that will be affected. There might be a few places where a Functor constraint has to be added alongside a Bifunctor constraint in situations like what you described, but I bet they're pretty rare, and that's a fairly small cost to bear. I could be wrong but I lean towards wanting to keep Wrap out and see what happens. My feeling is that long term, whether it's literally quantified constraints or some other means, the type system ought to be able to infer Functors from Bifunctors without any user-level code like Wrap.

[hdgarrood]

That's a good point, I hadn't looked at the commit. We could say we'll keep leaving them out for now and consider adding them back if we come across a situation where there isn't a good way of rewriting the code, then?

[JordanMartinez]

If we don't add Wrap back in, then the breaking change is that it's deleted. If we come across a situation where the best way to write some code is to use Wrap, then we can add it back to this repo a non-breaking change. Not so if we do vice versa.

Gary's in agreement with leaving it out. Harry seems to be ok with leaving it out. I'm curious to see whether @rhendric's claim holds true, so I think it should be left out, too.

With that being said, can this issue be closed?

[hdgarrood]

I think so 🙂