Re-use `Bifunctor` newtypes where appropriate
garyb opened this issue · 76 comments
For the next round of breaking-change releases.
See #22 (comment)
@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 cWe 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 instanceFunctor1 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 theProductwhich is already infunctorsnewtype 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.
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 cRight, 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.
@hdgarrood Can Clown really have a Functor1 instance?
EDIT: yes it can, b is phantom :)
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 gLooking over this issue, so the final class name should be FunctorR then rather than Functor1?
Given purescript/purescript-bifunctors#17, should we rather name it FunctorRight (or rename ApplyLeft, ApplicativeLeft, BindLeft and MonadLeft to ApplyL, ApplicativeL, BindL and MonadL)?
Using full words rather than abbreviations here sounds good to me.
I'll get started on this.
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)First PR here: purescript/purescript-functors#27
Why move Flip, Star, and Split, if they can be bifunctors/profunctors but not both?
Just wanted to remind people here that this PR is ready for review: purescript/purescript-functors#27
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.
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?
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.)
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?
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.
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.
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?)
Yeah 👍 merging into functors was what I had in mind.
But yes, true! Assuming the instances and whatnot all make sense too.
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.
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.
I’d suggest leaving contravariant alone, unless not merging it into functors causes problems.
Bitraversable, at least, extends Bifunctor, so either that class moves to functors or bifunctors remains as a dependency of foldable-traversable.
Ah of course, thanks. Do you think it’s fair to say that we can narrow down the options to these two then:
- Move all of the
Bi*classes (Bifunctor, Biapply, Biapplicative, Bifoldable, and Bitraversable) to functors, fully absorbing bifunctors into functors - Leave the
Bi*classes where they are - leave the bifunctors library just containing the class definitions of Bifunctor, Biapply, and Biapplicative, and leave the Bifoldable and Bitraversable classes in foldable-traversable, but move all of the data types (Clown, Joker, etc) into functors
Between those two options I’d prefer option 2, as I’d prefer not to have to move Bifoldable and Bitraversable out of foldable-traversable, since functors feels like an awkward place for them and also that feels like a breaking change that would be more likely to be felt by more people, I suspect.
Yeah, those two options are how that would work.
I like option 2 best as well.
I want to suggest a third option, although it might be too radical: lower either and tuples to the bottom of the dependency stack, raise foldable-traversable to the top, merge everything else into functors in the middle.
This would entail a lot of instances being moved to live with their classes instead of their data types, and Data.Tuple.lookup would have to be moved to Data.Foldable (or some other module in foldable-traversable), but on the whole I think this would cut through a lot of complexity without much more disruption than the functors merge would cause on its own, which we seemed willing to consider. (Or it could be my turn to miss the reason this can't work!)
@rhendric It might be. Would you be willing to graph the modules and their instances to see how it would play out?
I think moving either and tuples to the bottom is a good idea (assuming "bottom" means "everything else depends on this"). The easiest way to see if it will work is often to try it, I think!
Ok. Final graphs (I realize I forgot to include contravariant in the graph I posted above).
The below graphs take into consideration the following things stated either here or in the PR I opened:
- decision to drop
Wrapsince why would someone add aFunctorRightinstance but not aFunctorinstance - decision to not migrate
Joinbecause it can only be a Profunctor or Bifunctor but not both at the same time - decision to not migrate
SplitorStarbecause they can't be bifunctors - (my assumption) decision to merge
FlipandCowrapinto the same newtype.Cowrapseems to exist becauseFlipwas too far down in the dependency graph. I'm not sure what the implications of this change is
Current module dependency graph:

Option 2 module dependency graph (my understanding). White instances are being added rather than migrating from another package as this new dependency graph enables them to exist. Light-blue-backgrounds indicates the module is a part of the functors package:

The easiest way to see if it will work is often to try it, I think!
Then is someone else willing to do that? I created these graphs to be sure I'm not missing anything, but it feels like the ground keeps shifting from beneath my feet. In short, I'm losing motivation to continue working on this.
I'm trying out making everything depend on either/tuples. I'll post patches and graphs when I have something working. Didn't mean to create more work for you, @JordanMartinez!
Thanks! Also, one way for testing this idea out is to create your own forks of the necessary libraries, make the necessary changes, fork the package-sets repo's prepare-0.14 branch, override the repos to point to your forks, submit a PR that triggers CI, and then see what else is affected by this.
I tried it! Or, I guess, I'm trying it... I'm not sure how deep I ought to go in making the complete package set work. But the basic idea seems sound.
I had to get a few more packages involved than appeared in Jordan's excellent graphs, but here's the existing dependency structure:

The dotted line represents the possibility of merging those three packages together—I didn't do so in my patches, but from the dependency structure (which was generated automatically by output from purs graph), you can see that it would work, at least for this subset of packages. (It should work for the entire package set, I believe; it just isn't evident from the graph. I eyeball-checked each of the dependencies of those three packages to make sure that they themselves didn't take either of the others as a transitive dependency, which I think would be the only potential technical obstacle to the merge.)
The only new breaking change (relative to all the bifunctor/profunctor newtype unification previously discussed), as I suspected, was moving Data.Tuple.lookup to Data.Foldable, which I think is a better home for it anyway. I also added the instances colored white in the second graph in #23 (comment).
While many of these dependencies are freely reversible by moving instances between modules, there are a few that are forced (at least, as long as the relevant modules stay in their current packages):
- As previously noted,
BitraversableextendsBifunctorwhich forcesfoldable-traversable->bifunctors - The instance
Distributive f => Closed (Star f)forcesprofunctor->distributive - The instance
Profunctor p => Contravariant (Flip p b)forces eitherfunctors->profunctororcontravariant->profunctor, and the instanceContravariant f => Profunctor (Clown f)forces eitherfunctors->profunctororprofunctor->contravariant, which together forcefunctors->profunctor - The instance
Bifunctor p => Functor (Flip p a)forcesfunctors->bifunctor - The instance
Contravariant f => Bifunctor (Costar f), combined with the previous conclusion, forcesfunctors->contravariant
Beyond these constraints, I tried to give data type packages fewer dependencies by moving instances toward ‘classy’ packages, and to group functors with its two closest friends so that the case for merging them would be clearer. That pretty much uniquely determined this dependency graph.
Links to diffs are below:
bifunctors
const
contravariant
distributive
either
foldable-traversable
functors
identity
profunctor
tuples
This approach looks great to me! I completely agree that lookup is better situated in foldable-traversable too.
I think I remember putting lookup in tuples because the dependency graph was awkward to change at some point in the past 😄
This looks good. One small clarification. One of the other changes proposed in this issue was updating Bifunctor and Profunctor classes to depend on FunctorRight, right?
class FunctorRight f :: (Type -> Type -> Type) -> Constraint
class FunctorRight f where
rmap :: forall a b c. (a -> b) -> f c a -> f c b
class FunctorRight f <= 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 FunctorRight f <= 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 cIf so, then we can either make a new package called purescript-functor-right that exposes that type class and make bifunctors and profunctor both depend on it. Or we can merge bifunctors, profunctor, and functors into one new package as proposed earlier and add FunctorRight to that package, upcating the above two type classes as discussed.
@JordanMartinez, good points. I honestly forgot about that part of the plan. 😬
So, if we do indeed want FunctorRight as a superclass, then my vote goes toward merging. My read of the upthread comments is that there was interest in exploring FunctorRight as a superclass, but not necessarily consensus that it's the thing to do. Personally, I'm not really sold on the value of FunctorRight in the first place, but as long as it doesn't cost anything I have no objection to it. But using it as a superclass means an extra, basically always redundant, method to define on every Bifunctor and Profunctor instance. Couldn't we achieve almost the same thing by keeping the (distinct) Data.Bifunctor.Wrap and Data.Profunctor.Wrap newtypes and defining FunctorRight on them?
The point is to have a single rmap which works for every Bifunctor and every Profunctor, so that you don’t have to use imports to disambiguate. I don’t think having FunctorRight on just the Wrap newtypes achieves that.
Unless I suppose you wanted to do
rmap :: forall f a b c. Functor (f a) => (b -> c) -> f a b -> f a c
rmap = map
edit: arguably that doesn’t quite work, because without quantified constraints we can’t assert that f a has to be a functor for all a if f is to be a bifunctor/profunctor
But why is it important that rmap only works on things for which f a is a functor for all a? I'm just having trouble imagining a situation when I want to be generic about whether I'm using a bifunctor or a profunctor, but be very specific that I'm definitely using something that takes two parameters and is either covariantly or contravariantly functorial in the first, which I will then ignore because what I'm really here to do is map over the second. For cases where I don't care about the first argument, I think map suffices (although maybe type inference suffers or something, in which case the alias you proposed would help). For cases where I do care about the first argument, I probably care whether it's covariant or contravariant, and thus having to disambiguate doesn't seem bad to me.
I don’t think that it’s directly important that rmap works on every f for which f a is a functor, but I do think it’s important to have an analog of lmap which works for every Bifunctor and an analog of lcmap that works for every Profunctor for two reasons:
- so that someone reading code can immediately see that we are in fact mapping over the second argument of a Bifunctor/Profunctor rather than any other Functor which happens to be in scope; so that it’s obvious that this function is the counterpart to
lmap/lcmap - so that existing code that uses Bifunctor and Profunctor continues to work. We are already breaking the instances, but continuing to provide an
rmapallows us to avoid breaking all the code where people are making use of the existingrmapfunctions; breaking just the instances will be much less painful than breaking all the instances and all the downstream code that uses them.
Hm, suppose in this case the obvious answer which ought to make both of us happy is to just leave an rmap method in both the Bifunctor and Profunctor classes, then. The only thing that bothers me about that is that it’s annoying to have to disambiguate if you do want to have both rmaps in scope in one module, because we all know that underneath they are the same function.
Oh I'm sorry, I think I'm a little out of the loop... now that I'm looking for it, I see that in purescript/purescript-functors#27 there was mention of moving lmap into the Bifunctor class, which I now assume is part of a plan to also move lcmap into Profunctor (and replace bimap/dimap with rmap? or keep both?). If that has already been discussed elsewhere and agreed upon (is there a link someone can share please?), I have no additional objection to nominalizing FunctorRight as a superclass; my objections are all to breaking Bifunctor/Profunctor instances in this way in the first place.
I had thought we were debating between the status quo (two method-like functions named rmap which need disambiguation) and a FunctorRight superclass (one actual method named rmap, delete the method-like functions). I agree that having no rmaps at all would be bad, and that if lmap/lcmap are being promoted to methods, it makes sense to do so with rmap as well and then sharing the rmaps doesn't seem unreasonable.
I don't think you're out of the loop - I think most of the discussion does live here, apart from the Slack discussion I mentioned early in this thread (which will have been lost now anyway). In fact I had forgotten that the Bifunctor and Profunctor classes both only have one member, bimap and dimap respectively; I was incorrectly thinking that Bifunctor currently had members rmap and lmap, and that Profunctor currently had members rmap and lcmap. I'm not aware of any plan to make lmap and lcmap into members of their respective classes. I think the comment in purescript/purescript-functors#27 really just meant that you need a Bifunctor f instance to implement Functor (Flip f a).
Would moving lmap and lcmap into those classes be something we might want to do in the future?
Otherwise, it sounds like rhendric's forks can be merged into their corresponding repos, right?
Uh, clearly I need to pay more attention because @JordanMartinez was asking on this very issue yesterday about moving lmap and lcmap into their respective classes alongside bimap and dimap. After having thought about it, I don't think we should make lmap and lcmap into class members (either now or in the future), since their implementations should always be flip bimap identity and flip dimap identity respectively, and since it would be an annoying breaking change for non-obvious benefit.
But why is it important that rmap only works on things for which f a is a functor for all a? I'm just having trouble imagining a situation when I want to be generic about whether I'm using a bifunctor or a profunctor, but be very specific that I'm definitely using something that takes two parameters and is either covariantly or contravariantly functorial in the first, which I will then ignore because what I'm really here to do is map over the second.
I'm now persuaded by this. If I find myself wanting to import both rmap functions in one module, I agree that I should use qualified imports if I care about whether the first type parameter is contravariant or covariant, and if I don't care about what the first type parameter is doing, I should just use map.
Great! Sounds like we have a clear path to making the necessary changes and closing out this issue.
😬 I think we're really close. The last thing I think we need to hammer out is whether there ought to be FunctorRight instances for Split and Star and the Joins (I think that's the exhaustive list of all the two-parameter newtypes not yet FunctorRighted?). If yes, then we still need to answer the question of whether we do the functors merge or create a new package for FunctorRight. If no, we could still do the functors merge but if it'll save debate time I'm happy to cede that argument.
(Edit: Given the way the rmap discussion played out, I'm even less convinced of the value of FunctorRight; maybe we should even roll that addition back?)
😄 I think Harry was implying that FunctorRight is not needed. The goal of FunctorRight is to merge Bifunctor's rmap with Profunctor's rmap. However, Harry said,
If I find myself wanting to import both
rmapfunctions in one module, I agree that I should use qualified imports if I care about whether the first type parameter is contravariant or covariant, and if I don't care about what the first type parameter is doing, I should just usemap.
In other words:
- if I want to map the right parameter, and I care about it being covariant, I'll use
Bifunctor.rmap - if I want to map the right parameter, and I care about it being contravariant, I'll use
Profunctor.rmap - if I want to map the right parameter, and I don't care whether it's covariant or contravariant, I'll use
Functor.map
So, I think the last question to answer is whether to merge bifunctor, profunctor, and functors into functors. I think my vote is to keep them separate unless there is an instance that can't be written unless they are in the same library.
To be clear, you're saying let's not have a FunctorRight at all? (As opposed to let's have one but not care too much if some instances are missed?)
If that's what you mean, I agree with keeping the packages separate for expediency's sake and I'll get started ripping FunctorRight out of my branches.
I’m on board with removing FunctorRight too.
👍 for removing it, I was never quite following why it needed to exist given Functor 😄
Great, will do.
Should this entry in the changelog appear in the "Breaking Changes" section?
This package no longer depends on the
purescript-bifunctors, .... etc. packages. Relevant instances have been moved to those packages
A reasonable question; I wasn't sure myself. My thought was that removing these dependencies is non-breaking because anyone who needs those instances necessarily has both packages installed. A counter-argument might be that a consumer could be using modules from a package without explicitly depending on it, and in that case, removing a transitive dependency could cause a break (but one could also say that it just exposed something which was already broken).
There weren't any in this round of PRs but for the next round I was leaning towards adding new dependencies to the ‘Breaking Changes’ section, so I guess we should also talk about whether that's correct.
I think removing dependencies ideally shouldn’t be considered a breaking change; semver is really for tracking changes in your package’s public API, and your dependencies shouldn’t really be considered part of your package’s public API (otherwise you’d have to bump your package’s major version number all the time, and it would drown out useful information from changes in your package’s actual API). Choosing a set of versions which work together is the job of a solver or a package set curator, not of the package author via semver.
In practice, though, you can depend on packages “transitively” if you don’t declare them as dependencies, which means that you rely on one of your other dependencies depending on that package, so your package will stop compiling if the dependency is dropped. That’s not ideal, but I think there’s some work happening inside Spago to warn you if you’re depending on a module transitively like this.
In short: imo adding a dependency should never be considered breaking, and removing a dependency probably shouldn’t be considered breaking either, but it may be beneficial to consider dropping a dependency breaking as long as we don’t have tooling which helps prevent users from accidentally depending on transitive dependencies.
Well, the first round of PRs got merged with dropping dependencies as non-breaking features in the changelog, so if that's wrong that'll have to be changed when the changelogs get prepared for release, I guess. For consistency I think I'm going to stick to that for the rest of the PRs? I'll put added dependencies in the... ‘Other improvements’ section, I suppose?
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.
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)
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).
Only one more to go.
I've opened purescript/package-sets#807 to determine what else was affected by these changes.
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.
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.
It says
Wrapwas 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.
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.
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.
Yeah, agreed, it'd be nice to have quantified constraints but in the meantime Wrap is probably best.
(sorry!)
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.
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?
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?
I think so 🙂






