search

haskell / core-libraries-committee

95 stars 15 forks source link

Add quantified superclass to Bifunctor #91

Closed Icelandjack closed 1 year ago

Icelandjack commented 2 years ago

Add a quantified constraint forall a. Functor (bi a) to connect Bifunctor to Functor. The superclass logically follows from the meaning of Bifunctor and Edward Kmett has done the same for Profunctor in his own library.

{-# Language QuantifiedConstraints #-}

class (forall a. Functor (bi a)) => Bifunctor bi where
  ..

Here is a comment from Kmett about how Profunctor is waiting on this change in Bifunctor:

Once we have the superclass for Bifunctor we can fix the Cayley/Tannen split, which can then become one type.

I stalled a bit in actually doing this on my own primarily because Bifunctor moved into base and outside of my ability to unilaterally make the change. (Which means the bifunctors package is currently stuck because I can't line it up with the profunctors package HEAD until that superclass is in place.)

Related issues

Bodigrim commented 2 years ago

@Icelandjack I do not foresee technical objections, but are you up to an impact assessment?

Icelandjack commented 2 years ago

I made a merge request: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/9060. I haven't used clc-stackage, will have to look into it in the morning.

The instances in Data.Bifunctor necessitated three Functor instances

instance Functor ((,,,,) a b c d)
instance Functor ((,,,,,) a b c d e)
instance Functor ((,,,,,,) a b c d e f)

I took the liberty of making second a default definition (second = fmap) and weakening the minimal set from {-# Minimal bimap | first, second #-} to {-# Minimal bimap | first #-}.

Icelandjack commented 2 years ago

@Bodigrim Can you give me pointers for how to get clc-stackage running?

Icelandjack commented 2 years ago

Actually I probably don't have enough space on my computer to run that :smile: does submitting a CLC proposal really require people to compile all of Stackage which supposedly takes around 2 days?

treeowl commented 2 years ago

I have a significant concern about this proposal, even though I think it's ultimately the right thing: mismatched laziness for tuples. You write

A partially applied 'Bifunctor' must be a 'Functor' and
-- the 'second' method must agree with that 'fmap'. From this it
-- follows that:
--
-- @'second' 'id' = 'id'@

Putting this more concisely, there should be a law

@'second' = 'fmap'@

But that is not the case for tuples! We have

fmap id (_|_ :: (a, b)) = _|_
second id (_|_ :: (a, b)) = (_|_, _|_)

The reason for this, as I understand it, is that the bifunctors package wanted Data.Bifunctor.first and Data.Bifunctor.second to agree with Control.Arrow.first and Control.Arrow.second, which are lazy to work well with ArrowLoop. But it's really quite a nasty mismatch, and much more so once Functor and Bifunctor are more formally tied together.

I would want to redefine the Bifunctor instances for tuples to be strict (which will also require making their Biapplicative instances strict again; I recently moved to have those changed for consistency with Bifunctor). Then I'd want a newtype like

newtype LazyTup a b = LazyTup (a, b)
instance Functor (LazyTup a) where
  fmap f (LazyTup ~(a, b)) = (a, f b)
instance Bifunctor LazyTup where
  bimap f g (LazyTup ~(a, b)) = (f a, g b)
instance Biapplicative LazyTup where
  bipure a b = LazyTup (a, b)
  biliftA2 f g (LazyTup ~(a, b)) (LazyTup ~(c, d))= LazyTup ((f a c), (g b d))
Bodigrim commented 2 years ago

Actually I probably don't have enough space on my computer to run that 😄 does submitting a CLC proposal really require people to compile all of Stackage which supposedly takes around 2 days?

Yes.

treeowl commented 2 years ago

@Bodigrim , that's pretty classist. Change your policy so people who aren't rich can still make proposals.

Bodigrim commented 2 years ago

@treeowl I'm not in a good humour today. If people expect unpaid volunteers to take their proposals seriously, they can certainly spare 48 machine hours and couple gigabytes of hard drive to prepare an impact assessment.

Bodigrim commented 2 years ago

I have a significant concern about this proposal, even though I think it's ultimately the right thing: mismatched laziness for tuples.

Potentially we can split the proposal into two: one adding a superclass, and another adding a law second = fmap and fixing mismatch for tuples.

treeowl commented 2 years ago

@Bodigrim , as you've effectively banned me from making proposals from two different directions, that's not a viable path at all.

Bodigrim commented 2 years ago

@treeowl I'm sorry?

L-as commented 2 years ago

It seems like this is something that could be automated to some extent? Iceland Jack only has a toaster available AFAIK.

treeowl commented 2 years ago

I also have just one old laptop and I need to use it to compile stuff for work. I don't have the computational cycles or likely even storage available to compile all of Stackage.

Bodigrim commented 2 years ago

It seems like this is something that could be automated to some extent?

It's kinda already automated to cloning clc-stackage and running cabal build, right?

Iceland Jack only has a toaster available AFAIK.

If this toaster is capable to build GHC, it is likely capable to build Stackage as well.

I also have just one old laptop and I need to use it to compile stuff for work. I don't have the computational cycles or likely even storage available to compile all of Stackage.

I also have a single underpowered laptop with a very limited storage. It serves me well for CLC impact assessment.

L-as commented 2 years ago

With automated, I mean way by which you can easily submit a patch, and a remote server provisioned by e.g. the Haskell Foundation so that people with toasters or from poor or undeveloped countries can still contribute to Haskell. This is usually just CI, and compiling all of Stackage on PRs to base seems reasonable to me.

chreekat commented 2 years ago

With automated, I mean way by which you can easily submit a patch, and a remote server provisioned by e.g. the Haskell Foundation so that people with toasters or from poor or undeveloped countries can still contribute to Haskell. This is usually just CI, and compiling all of Stackage on PRs to base seems reasonable to me.

I think we're 99% of the way there. GHC CI already compiles HEAD against head.hackage nearly every night, and head.hackage is nearly Stackage.

Adding a manual job to the pipeline that clones clc-stackage and builds it with the compiler built in an earlier step, a la the perf-nofib job, may be all that is required. At least for changes to boot libraries. (Some details and opinions elided. Open an issue on the GHC tracker and/or a MR adding this job if you want to discuss it more. As much as I would like to just do it myself, I would also like to make CI overall more reliable, so I'm focusing on that first.)

Ericson2314 commented 2 years ago

Yeah I agree this feels very clearly like a thing where the Haskell Foundation should step in and make it as easy as possible. I think it is good if people feel it is easy to contribute to important library's design / it being harder to do regression tests doesn't feel like the right way to deal with Eternal September problems (which can be real but not saying anyone is trying on purpose to put up barriers entry).

Bodigrim commented 2 years ago

Proposers are welcome to do impact assessment themselves, ask a friend, pray for a miracle or HF. Anything goes. I don't buy the claim that it is disproportionately difficult; plenty of people figured out how to do it before.

With automated, I mean way by which you can easily submit a patch, and a remote server provisioned by e.g. the Haskell Foundation so that people with toasters or from poor or undeveloped countries can still contribute to Haskell. This is usually just CI, and compiling all of Stackage on PRs to base seems reasonable to me.

Impact assessment is not a binary characteristic. If a package fails to build, a proposer is supposed to clone it with cabal unpack, patch locally, link into cabal.project and give it another go. This is an interactive process; CI approach does not really fit well here.

Anyway, this is all off topic. If there is an interest to discuss this digression further, please create a separate issue.

sjakobi commented 2 years ago

On the topic of building clc-stackage, note that you don't have to build all of it in one sitting. You can always Ctrl-C and continue at another time. Nor does the build process need to use all your cores, you can limit it to e.g. 2 processes with -j2.

It would be good to document how much disk space it requires though.

Bodigrim commented 2 years ago

Thanks @sjakobi, excellent points. I've updated https://github.com/Bodigrim/clc-stackage#how-to.

@Icelandjack what do you think?

Bodigrim commented 1 year ago

@Icelandjack just a gentle reminder about your proposal here.

Topsii commented 1 year ago

Issues Building clc-stackage

I tried to build clc-stackage, but I hit an error that I don't understand.

Tobias@DESKTOP-RODILQ3 MINGW64 /e/ghc-bifunctors/clc-stackage
$ cabal build -w "E:\ghc-bifunctors\ghc\_build\stage1\bin\ghc-bifunctor.exe" --keep-going --constraint="HsOpenSSL +use-pkg-config" --constraint="pcre-light +use-pkg-config" --constraint="hmatrix +openblas" --constraint="hexpat +bundle"
Build profile: -w ghc-9.2.4 -O1
In order, the following will be built (use -v for more details):
 - clc-stackage-0.1.0.0 (lib) (first run)
cabal-3.6.2.0.exe: Failed to build clc-stackage-0.1.0.0. The failure occurred
during the configure step. The exception was:
C:\ghcup\bin\cabal-3.6.2.0.exe: createProcess: does not exist (No such file or
directory)

Though I think I have built most/all packages. Here's the -v3 output.

I have removed 70 packages from build-depends. Most are only supposed to work on Unix. A few have build-type: configure scripts that I could not get to work or dependencies that I was not able to supply. The katip packages and beam-sqlite only work with an older version of the Win32 package. fsevents is Mac only. ki, path-extra and krank has template haskell failures that seemed unrelated:

Click to see TH failures ``` • Exception when trying to run compile-time code: InvalidAbsDir "/" CallStack (from HasCallStack): error, called at src\\Path\\Include.hs:759:20 in path-0.9.2-inplace:Path.Windows Code: template-haskell-2.18.0.0:Language.Haskell.TH.Quote.quoteExp absdir "/" • In the quasi-quotation: [absdir|/|] | 106 | [] -> pure (Left [absdir|/|]) | ``` ``` src\Krank\Checkers\Ignore.hs:35:31: error: • Exception when trying to run compile-time code: src\PyF\Internal\Meta.hs:(212,1)-(347,76): Non-exhaustive patterns in function translateTHtoGHCExt Code: template-haskell-2.18.0.0:Language.Haskell.TH.Quote.quoteExp fmt "Impossible case, update the guard with: {ByteString.unpack command}" • In the quasi-quotation: [fmt|Impossible case, update the guard with: {ByteString.unpack command}|] | 35 | | otherwise = error [fmt|Impossible case, update the guard with: {ByteString.unpack command}|] | ```
Click to show all 70 excluded packages ``` airship ==0.9.5, aura ==3.2.9, beam-sqlite ==0.5.1.2, bimap-server ==0.1.0.1, bindings-uname ==0.1, blas-hs ==0.1.1.0, brick ==0.69, bytestring-mmap ==0.2.2, check-email ==1.0.2, climb ==0.3.3, connection-pool ==0.2.2, core-program ==0.5.0.4, core-telemetry ==0.2.3.5, cryptonite-openssl ==0.7, curl ==1.3.8, cursor-brick ==0.1.0.1, dbus ==1.2.24, dbus-hslogger ==0.1.0.1, debian ==4.0.2, download ==0.3.2.7, download-curl ==0.1.4, editor-open ==0.6.0.0, exit-codes ==1.0.0, faktory ==1.1.2.2, fdo-notify ==0.3.1, filter-logger ==0.6.0.0, glob-posix ==0.2.0.1, hdaemonize ==0.5.6, hfsevents ==0.1.6, hledger-iadd ==1.3.17, hsyslog ==5.0.2, hxt-curl ==9.1.1.1, katip ==0.8.7.2, katip-logstash ==0.1.0.2, katip-wai ==0.1.2.0, ki ==0.2.0.1, krank ==0.2.3, linenoise ==0.3.2, logging-facade-syslog ==1, magic ==1.1, microlens-process ==0.2.0.2, nvim-hs ==2.2.0.2, OpenAL ==1.7.0.5, pager ==0.1.1.0, path-extra ==0.2.0, pid1 ==0.1.3.0, poll ==0.0.0.2, posix-paths ==0.3.0.0, posix-pty ==0.2.2, projectroot ==0.2.0.1, rainbow ==0.34.2.2, rainbox ==0.26.0.0, rawfilepath ==1.0.1, resolv ==0.1.2.0, safe-coloured-text-terminfo ==0.0.0.0, safeio ==0.0.5.0, sandwich ==0.1.0.9, shared-memory ==0.2.0.0, shell-conduit ==5.0.0, simple-cmd ==0.2.6, status-notifier-item ==0.3.1.0, systemd ==2.3.0, termbox ==0.3.0, terminfo, unix, unix-bytestring ==0.3.7.7, vty ==5.35.1, warp-tls-uid ==0.2.0.6, Xauth ==0.1, xdg-desktop-entry ==0.1.1.1 ```

Impact assessment

I have only applied this patch to GHC 9.2. I have left Bifoldable and Bitraversable unchanged.

The build errors all relate to missing Functor instances. Some of them also had Bifoldable and Bitraversable instances but no Foldable and Traversable instances.

Besides that I saw that for GenericBifunctor from the generic-functor package the docs do not suggest to derive the Functor instance via GenericBifunctor but via GenericFunctor. If Functor is going to be a superclass of Bifunctor, shouldn't it be advised to derive the required superclass instance via the same newtype? That is the only documentation issue I noticed.

I also saw that Tree in Data.Geometry.QuadTree.Tree from the hgeometry package has Bifoldable1 and Bitraversable1 instances but no Foldable1 and Traversable1 instances.

Perhaps it makes sense to define default methods similar to fmapDefault and foldMapDefault in Data.Bitraversable to derive Bifunctor and Bifoldable in terms of an existing Bitraversable instance?

  foldMapDefault = bifoldMap (const mempty)
  traverseDefault = bitraverse pure

Here is the full list of build errors:

Bodigrim commented 1 year ago

Thanks @Topsii. Could you plesase share the patches you made for affected packages? For example, fork them, patch and provide cabal.project pointing to patched repos. This way someone with a UNIX machine would be able to continue your work and check the rest of the packages. It is also important for CLC to see the patches in full to understand how much effort are required on average to implement this proposal.

That said, the amound of breakage does not seem prohibiting to me, and all affected package can be patched in a backwards-compatible way.

What's your stance on https://github.com/haskell/core-libraries-committee/issues/91#issuecomment-1256716483, @Icelandjack?

Topsii commented 1 year ago

generic-functor

Due to this proposal the documentation for GenericBifunctor in the generic-functor package became more complex. The type is intended to be used to generically derive Bifunctor and Bifoldable instances for other types. The documentation now reads:

Note: although GenericBifunctor has Functor and Foldable instances, it is recommended to use GenericFunctor instead for those two classes. They have to use a separate deriving clause from Bifunctor and Bifoldable anyway. Those instances exist because they are to become superclasses of Bifunctor and Bifoldable. The Foldable instance of GenericBifunctor is also less efficient than GenericFunctor unless the extra const mempty gets optimized away.

Impact assessment for Foldable and Traversable

The impact assessment for Foldable and Traversable uncovered the following build failures. I am unsure whether my fix for Coyoneda is acceptable, because I do not know the motivation behind this datatype.

cabal.project

Here's a cabal.project pointing to the patched repos. cabal.zip I did not compile aura, because its newest version introduced a dependency on unix. Though I have included the patched aura package in comments. I also did not include my manual patches to text-icu, hmatrix and c14n. There I had inserted pkgconfig-depends to use MSYS2 packages with .pc files.

Removal of second

It may be dangerous to remove second from the set of methods needed for a minimal complete instance of Bifunctor. Specifically it is dangerous to change the default definition of second from bimap id to fmap. Suppose someone had previously defined their instances like this:

instance Functor CustomDataType where
  fmap = second

instance Bifunctor CustomDataType where
  bimap = actual implementation

Then any call of either fmap or second would loop.

Such cases are not considered in my impact assessment, as they are not easy to detect.

I assume the goal is to remove second from Bifunctor at some point in the future? The situation seems somewhat similar to the monad of no return proposal with the difference that there is more than one possible minimal complete set for Bifunctor. And obviously Bifunctor is not as widely used as Monad. Perhaps there should be a warning flag -Wnoncanonical-bifunctor-instances similar to the already existing -Wnoncanonical-monad-instances and -Wnoncanonical-monoid-instances?

Migration Plan?

If the goal is to remove second from the class, change its definition to fmap and remove it from the complete set, then perhaps it is safer to do so only after some time has passed with -Wnoncanonical-bifunctor-instances enabled by default? Would -Wnoncanonical-bifunctor-instances even warn in the example above where second was not explicitely defined?

I am not happy with such a plan, because it would require library authors to change their code twice:

  1. change the definition of second to second = fmap such that the warning does not apply
  2. much later: remove the definition of second

foreach quantifier

There is an accepted GHC proposal of a design for Dependent Types, which plans to introduce a foreach qualifier. I am not sure how this is going to interact with the QuantifiedConstraints language extension, but I can likewise imagine a definition of Bifunctor with an foreach quantified superclass.

{-# Language QuantifiedConstraints #-}

class (foreach a. Functor (p a)) => Bifunctor p where
  ..

In a world with the foreach quantifier we might still want to have Functor as a quantified superclass of Bifunctor for some quantifier, foreach or forall. Perhaps we can easily relax the superclass constraint later by replacing forall with foreach. I just wanted to mention this for the sake of completeness.

Bodigrim commented 1 year ago

Thanks @Topsii, excellent work!

The impact assessment for Foldable and Traversable uncovered the following build failures.

Are you referring to #93? Let's leave it for another day and stick to the Bifunctor proposal at hand for time being.

I assume the goal is to remove second from Bifunctor at some point in the future?

I don't think so, and the proposal does not mention it. We have not removed mappend from Monoid or return from Monad, so I do not see second removed from Bifunctor in foreseeable future.

With regards to instance Bifunctor (,) I realised that the proposal does not make things worse than they are right now. Haddocks already require that first id = id and second id = id, which is not precisely true for tuples. That's pretty unfortunate indeed, but it is pre-existing state of affairs and should be resolved separately of this proposal.

That said, I don't see any specific obstacles to move the proposal forward. @Icelandjack @treeowl any comments?

treeowl commented 1 year ago

As long as we actually do something about the strictness issue.

Bodigrim commented 1 year ago

(The issue with first id for tuples is the same as with fmap id for NonEmpty - both are lazy beyond measure. It would be nice to fix it somehow, but that's really a separate issue common for entities from kmettoverse)

Topsii commented 1 year ago

The impact assessment for Foldable and Traversable uncovered the following build failures.

Are you referring to #93?

Yes.

Let's leave it for another day and stick to the Bifunctor proposal at hand for time being.

It just made sense for me to do the impact assessment for this proposal and #93 in one go, because whenever a Functor instance was missing half the time Foldable/Traversable instances were missing too. I did not mean to give priority to #93 or anything like that.

Maybe I wasn't clear enough: @Icelandjack wrote:

I made a merge request: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/9060. [...] I took the liberty of making second a default definition (second = fmap) and weakening the minimal set from {-# Minimal bimap | first, second #-} to {-# Minimal bimap | first #-}.

I think we should not take this liberty if there is no plan to remove second. In my previous comment I gave an example how it can go wrong.

Bodigrim commented 1 year ago

I think we should not take this liberty if there is no plan to remove second. In my previous comment I gave an example how it can go wrong.

Your example demonstrates that changing the implementation of second from bimap id to fmap is dangerous, because it can cause recursive loops in instances, which were sane previously. Makes sense, thanks.

@Icelandjack we can't really proceed any further without an active proposer. Are you still interested to pursue this? @Topsii would you like to take over?

Icelandjack commented 1 year ago

Yes @Topsii can take over

Bodigrim commented 1 year ago

@Topsii are you interested to take over this proposal?

Topsii commented 1 year ago

@Topsii are you interested to take over this proposal?

Sure.

I have opened a merge request where second remains in the minimal set (and the definition of second remains the same).

However I am still pondering whether there should be a long term plan to remove second from the class/minimal set. I would certainly like the CLC to decide on this, as they consider this proposal. Clearly if we are ever going to bother people with canonicalizing their Bifunctor instances in the future, then the sooner we do it, the less work will be necessary. I am aware that the bar for the removal is high. Hence I want to offer a possible migration path towards removal and let the CLC decide how far they want to go.

You wrote

I assume the goal is to remove second from Bifunctor at some point in the future?

I don't think so, and the proposal does not mention it. We have not removed mappend from Monoid or return from Monad, so I do not see second removed from Bifunctor in foreseeable future.

But for Monoid and Monad we have warnings turned on by default that prevent people from writing noncanonical instances wrt to Monoid or Monad. With these noncanonical warnings we keep the option open to remove the class methods in the (unforeseeable?) future. We can imagine the same for Bifunctor. I had previously overlooked that these flags also warn about noncanonical backwards definitions. For Bifunctor a noncanonical backwards definition would be a Functor instance that defines fmap = second.

Moreover Monoid and Monad are used much more frequently than Bifunctor. An approximate search on Hackage yields 5992, 3977 and 418 non-derived instances of Monoid, Monad and Bifunctor respectively.

Further historically it was necessary to define mappend/return, whereas it was optional to define second. The vast majority of the 418 Bifunctor instances only define bimap and thus omit second. There are 86 instances (~20%) that do define second. From these 34 (~40%) define second = fmap. Conversely 52 Bifunctor instances on Hackage are noncanonical. There are 14 Functor instances that are backwards noncanonical wrt Bifunctor.

Click to see which of the 86 Bifunctor instances defining second are canonical/noncanonical #### second is defined as fmap [https://hackage-search.serokell.io/viewfile/acquire-0.3.1/library/Acquire.hs#line-72](https://hackage-search.serokell.io/viewfile/acquire-0.3.1/library/Acquire.hs#line-72) [https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-97](https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-97) [https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-109](https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-109) [https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-117](https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-117) [https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-134](https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-134) [https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-176](https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-176) [https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-203](https://hackage-search.serokell.io/viewfile/capnp-0.16.0.0/cmd/capnpc-haskell/IR/Common.hs#line-203) [https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-226](https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-226) [https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-296](https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-296) [https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-369](https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-369) [https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-400](https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-400) [https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-726](https://hackage-search.serokell.io/viewfile/dhall-1.41.2/src/Dhall/Syntax.hs#line-726) [https://hackage-search.serokell.io/viewfile/ditto-0.4.1/src/Ditto/Core.hs#line-166](https://hackage-search.serokell.io/viewfile/ditto-0.4.1/src/Ditto/Core.hs#line-166) [https://hackage-search.serokell.io/viewfile/foldl-transduce-0.6.0.1/src/Control/Foldl/Transduce.hs#line-228](https://hackage-search.serokell.io/viewfile/foldl-transduce-0.6.0.1/src/Control/Foldl/Transduce.hs#line-228) [https://hackage-search.serokell.io/viewfile/foldl-transduce-0.6.0.1/src/Control/Foldl/Transduce.hs#line-299](https://hackage-search.serokell.io/viewfile/foldl-transduce-0.6.0.1/src/Control/Foldl/Transduce.hs#line-299) [https://hackage-search.serokell.io/viewfile/fresnel-0.0.0.1/src/Fresnel/Profunctor/Recall.hs#line-25](https://hackage-search.serokell.io/viewfile/fresnel-0.0.0.1/src/Fresnel/Profunctor/Recall.hs#line-25) [https://hackage-search.serokell.io/viewfile/generic-functor-1.1.0.0/src/Generic/Functor/Internal.hs#line-405](https://hackage-search.serokell.io/viewfile/generic-functor-1.1.0.0/src/Generic/Functor/Internal.hs#line-405) [https://hackage-search.serokell.io/viewfile/hledger-lib-1.27.1/Hledger/Reports/ReportTypes.hs#line-104](https://hackage-search.serokell.io/viewfile/hledger-lib-1.27.1/Hledger/Reports/ReportTypes.hs#line-104) [https://hackage-search.serokell.io/viewfile/kempe-0.2.0.12/src/Kempe/AST.hs#line-71](https://hackage-search.serokell.io/viewfile/kempe-0.2.0.12/src/Kempe/AST.hs#line-71) [https://hackage-search.serokell.io/viewfile/kempe-0.2.0.12/src/Kempe/AST.hs#line-130](https://hackage-search.serokell.io/viewfile/kempe-0.2.0.12/src/Kempe/AST.hs#line-130) [https://hackage-search.serokell.io/viewfile/kempe-0.2.0.12/src/Kempe/AST.hs#line-232](https://hackage-search.serokell.io/viewfile/kempe-0.2.0.12/src/Kempe/AST.hs#line-232) [https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Types.hs#line-2524](https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Types.hs#line-2524) [https://hackage-search.serokell.io/viewfile/nice-html-0.4.1/src/Text/Html/Nice/FreeMonad.hs#line-181](https://hackage-search.serokell.io/viewfile/nice-html-0.4.1/src/Text/Html/Nice/FreeMonad.hs#line-181) [https://hackage-search.serokell.io/viewfile/pipes-key-value-csv-0.4.0.3/src/Data/Validation.hs#line-92](https://hackage-search.serokell.io/viewfile/pipes-key-value-csv-0.4.0.3/src/Data/Validation.hs#line-92) [https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-99](https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-99) [https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-321](https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-321) [https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-387](https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-387) [https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-403](https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-403) [https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-452](https://hackage-search.serokell.io/viewfile/plan-applicative-2.0.1.0/lib/Control/Plan/Core.hs#line-452) [https://hackage-search.serokell.io/viewfile/retroclash-lib-0.1.2.1/src/RetroClash/Port.hs#line-31](https://hackage-search.serokell.io/viewfile/retroclash-lib-0.1.2.1/src/RetroClash/Port.hs#line-31) [https://hackage-search.serokell.io/viewfile/selections-0.3.0.0/src/Data/Functor/Selection.hs#line-66](https://hackage-search.serokell.io/viewfile/selections-0.3.0.0/src/Data/Functor/Selection.hs#line-66) [https://hackage-search.serokell.io/viewfile/stgi-1.1/src/Stg/Util.hs#line-39](https://hackage-search.serokell.io/viewfile/stgi-1.1/src/Stg/Util.hs#line-39) [https://hackage-search.serokell.io/viewfile/streaming-bracketed-0.1.1.0/library/Streaming/Bracketed/Internal.hs#line-41](https://hackage-search.serokell.io/viewfile/streaming-bracketed-0.1.1.0/library/Streaming/Bracketed/Internal.hs#line-41) [https://hackage-search.serokell.io/viewfile/transaction-0.1.1.3/src/Data/Transaction.hs#line-113](https://hackage-search.serokell.io/viewfile/transaction-0.1.1.3/src/Data/Transaction.hs#line-113) #### second is defined but not as fmap [https://hackage-search.serokell.io/viewfile/ForestStructures-0.0.1.0/Data/Forest/StructuredPaired.hs#line-45](https://hackage-search.serokell.io/viewfile/ForestStructures-0.0.1.0/Data/Forest/StructuredPaired.hs#line-45) [https://hackage-search.serokell.io/viewfile/base-4.17.0.0/Data/Bifunctor.hs#line-112](https://hackage-search.serokell.io/viewfile/base-4.17.0.0/Data/Bifunctor.hs#line-112) [https://hackage-search.serokell.io/viewfile/basement-0.0.15/Basement/Compat/Bifunctor.hs#line-84](https://hackage-search.serokell.io/viewfile/basement-0.0.15/Basement/Compat/Bifunctor.hs#line-84) [https://hackage-search.serokell.io/viewfile/basement-cd-0.0.12.1/Basement/Compat/Bifunctor.hs#line-84](https://hackage-search.serokell.io/viewfile/basement-cd-0.0.12.1/Basement/Compat/Bifunctor.hs#line-84) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/old-src/ghc709/Data/Bifunctor.hs#line-97](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/old-src/ghc709/Data/Bifunctor.hs#line-97) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Biff.hs#line-137](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Biff.hs#line-137) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Clown.hs#line-162](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Clown.hs#line-162) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Flip.hs#line-106](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Flip.hs#line-106) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Joker.hs#line-161](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Joker.hs#line-161) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Product.hs#line-129](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Product.hs#line-129) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Sum.hs#line-116](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Sum.hs#line-116) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Tannen.hs#line-154](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Tannen.hs#line-154) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Wrapped.hs#line-131](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/src/Data/Bifunctor/Wrapped.hs#line-131) [https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/tests/BifunctorSpec.hs#line-345](https://hackage-search.serokell.io/viewfile/bifunctors-5.5.13/tests/BifunctorSpec.hs#line-345) [https://hackage-search.serokell.io/viewfile/chiasma-0.10.0.0/lib/Chiasma/Ui/Data/View.hs#line-105](https://hackage-search.serokell.io/viewfile/chiasma-0.10.0.0/lib/Chiasma/Ui/Data/View.hs#line-105) [https://hackage-search.serokell.io/viewfile/chiasma-0.10.0.0/lib/Chiasma/Ui/Data/View.hs#line-121](https://hackage-search.serokell.io/viewfile/chiasma-0.10.0.0/lib/Chiasma/Ui/Data/View.hs#line-121) [https://hackage-search.serokell.io/viewfile/descriptive-0.9.5/src/Descriptive.hs#line-108](https://hackage-search.serokell.io/viewfile/descriptive-0.9.5/src/Descriptive.hs#line-108) [https://hackage-search.serokell.io/viewfile/elynx-tree-0.7.0.1/src/ELynx/Tree/Rooted.hs#line-142](https://hackage-search.serokell.io/viewfile/elynx-tree-0.7.0.1/src/ELynx/Tree/Rooted.hs#line-142) [https://hackage-search.serokell.io/viewfile/fgl-5.8.0.0/Data/Graph/Inductive/PatriciaTree.hs#line-143](https://hackage-search.serokell.io/viewfile/fgl-5.8.0.0/Data/Graph/Inductive/PatriciaTree.hs#line-143) [https://hackage-search.serokell.io/viewfile/fgl-5.8.0.0/Data/Graph/Inductive/Tree.hs#line-144](https://hackage-search.serokell.io/viewfile/fgl-5.8.0.0/Data/Graph/Inductive/Tree.hs#line-144) [https://hackage-search.serokell.io/viewfile/haggle-0.2/src/Data/Graph/Haggle/PatriciaTree.hs#line-48](https://hackage-search.serokell.io/viewfile/haggle-0.2/src/Data/Graph/Haggle/PatriciaTree.hs#line-48) [https://hackage-search.serokell.io/viewfile/lifted-protolude-0.1.6/src/Bifunctor.hs#line-21](https://hackage-search.serokell.io/viewfile/lifted-protolude-0.1.6/src/Bifunctor.hs#line-21) [https://hackage-search.serokell.io/viewfile/linear-base-0.3.0/src/Data/Bifunctor/Linear/Internal/Bifunctor.hs#line-38](https://hackage-search.serokell.io/viewfile/linear-base-0.3.0/src/Data/Bifunctor/Linear/Internal/Bifunctor.hs#line-38) [https://hackage-search.serokell.io/viewfile/linear-base-0.3.0/src/Data/Bifunctor/Linear/Internal/Bifunctor.hs#line-48](https://hackage-search.serokell.io/viewfile/linear-base-0.3.0/src/Data/Bifunctor/Linear/Internal/Bifunctor.hs#line-48) [https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Bounds.hs#line-73](https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Bounds.hs#line-73) [https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Types.hs#line-2220](https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Types.hs#line-2220) [https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Types.hs#line-2225](https://hackage-search.serokell.io/viewfile/liquidhaskell-0.8.10.7/src/Language/Haskell/Liquid/Types/Types.hs#line-2225) [https://hackage-search.serokell.io/viewfile/math-programming-0.4.0/src/Math/Programming/Types.hs#line-243](https://hackage-search.serokell.io/viewfile/math-programming-0.4.0/src/Math/Programming/Types.hs#line-243) [https://hackage-search.serokell.io/viewfile/mediabus-0.4.0.1/src/Data/MediaBus/Basics/Series.hs#line-59](https://hackage-search.serokell.io/viewfile/mediabus-0.4.0.1/src/Data/MediaBus/Basics/Series.hs#line-59) [https://hackage-search.serokell.io/viewfile/monus-weighted-search-0.1.0.0/src/Control/Monad/Heap.hs#line-112](https://hackage-search.serokell.io/viewfile/monus-weighted-search-0.1.0.0/src/Control/Monad/Heap.hs#line-112) [https://hackage-search.serokell.io/viewfile/multi-except-0.3.0.0/test/Test/Bifunctor.hs#line-18](https://hackage-search.serokell.io/viewfile/multi-except-0.3.0.0/test/Test/Bifunctor.hs#line-18) [https://hackage-search.serokell.io/viewfile/neither-data-0.2.3.4/Data/Neither.hs#line-177](https://hackage-search.serokell.io/viewfile/neither-data-0.2.3.4/Data/Neither.hs#line-177) [https://hackage-search.serokell.io/viewfile/noether-0.0.1/library/Lemmata/Bifunctor.hs#line-21](https://hackage-search.serokell.io/viewfile/noether-0.0.1/library/Lemmata/Bifunctor.hs#line-21) [https://hackage-search.serokell.io/viewfile/optics-core-0.4.1/src/Optics/Internal/Bi.hs#line-18](https://hackage-search.serokell.io/viewfile/optics-core-0.4.1/src/Optics/Internal/Bi.hs#line-18) [https://hackage-search.serokell.io/viewfile/optics-core-0.4.1/src/Optics/Re.hs#line-130](https://hackage-search.serokell.io/viewfile/optics-core-0.4.1/src/Optics/Re.hs#line-130) [https://hackage-search.serokell.io/viewfile/pgp-wordlist-0.1.0.3/src/Data/Text/PgpWordlist/Internal/AltList.hs#line-89](https://hackage-search.serokell.io/viewfile/pgp-wordlist-0.1.0.3/src/Data/Text/PgpWordlist/Internal/AltList.hs#line-89) [https://hackage-search.serokell.io/viewfile/profunctor-optics-0.0.2/src/Data/Profunctor/Optic/Types.hs#line-307](https://hackage-search.serokell.io/viewfile/profunctor-optics-0.0.2/src/Data/Profunctor/Optic/Types.hs#line-307) [https://hackage-search.serokell.io/viewfile/profunctor-optics-0.0.2/src/Data/Profunctor/Optic/Types.hs#line-330](https://hackage-search.serokell.io/viewfile/profunctor-optics-0.0.2/src/Data/Profunctor/Optic/Types.hs#line-330) [https://hackage-search.serokell.io/viewfile/protolude-0.3.2/src/Protolude/Bifunctor.hs#line-25](https://hackage-search.serokell.io/viewfile/protolude-0.3.2/src/Protolude/Bifunctor.hs#line-25) [https://hackage-search.serokell.io/viewfile/streaming-0.2.3.1/src/Data/Functor/Of.hs#line-52](https://hackage-search.serokell.io/viewfile/streaming-0.2.3.1/src/Data/Functor/Of.hs#line-52) [https://hackage-search.serokell.io/viewfile/streamly-0.8.3/src/Streamly/Internal/Data/Fold/Step.hs#line-55](https://hackage-search.serokell.io/viewfile/streamly-0.8.3/src/Streamly/Internal/Data/Fold/Step.hs#line-55) [https://hackage-search.serokell.io/viewfile/streamly-0.8.3/src/Streamly/Internal/Data/Parser/ParserD/Type.hs#line-209](https://hackage-search.serokell.io/viewfile/streamly-0.8.3/src/Streamly/Internal/Data/Parser/ParserD/Type.hs#line-209) [https://hackage-search.serokell.io/viewfile/strict-0.4.0.1/src/Data/Strict/Either.hs#line-187](https://hackage-search.serokell.io/viewfile/strict-0.4.0.1/src/Data/Strict/Either.hs#line-187) [https://hackage-search.serokell.io/viewfile/strict-0.4.0.1/src/Data/Strict/Tuple.hs#line-194](https://hackage-search.serokell.io/viewfile/strict-0.4.0.1/src/Data/Strict/Tuple.hs#line-194) [https://hackage-search.serokell.io/viewfile/strict-base-0.4.0.0/src/Data/Strict/Either.hs#line-53](https://hackage-search.serokell.io/viewfile/strict-base-0.4.0.0/src/Data/Strict/Either.hs#line-53) [https://hackage-search.serokell.io/viewfile/strict-base-0.4.0.0/src/Data/Strict/Tuple.hs#line-67](https://hackage-search.serokell.io/viewfile/strict-base-0.4.0.0/src/Data/Strict/Tuple.hs#line-67) [https://hackage-search.serokell.io/viewfile/these-skinny-0.7.5/Data/These.hs#line-202](https://hackage-search.serokell.io/viewfile/these-skinny-0.7.5/Data/These.hs#line-202) [https://hackage-search.serokell.io/viewfile/tidal-1.9.2/test/Sound/Tidal/PatternTest.hs#line-38](https://hackage-search.serokell.io/viewfile/tidal-1.9.2/test/Sound/Tidal/PatternTest.hs#line-38) [https://hackage-search.serokell.io/viewfile/transformers-0.6.0.4/Data/Functor/Constant.hs#line-155](https://hackage-search.serokell.io/viewfile/transformers-0.6.0.4/Data/Functor/Constant.hs#line-155) [https://hackage-search.serokell.io/viewfile/transformers-compat-0.7.2/src/Control/Monad/Trans/Instances.hs#line-344](https://hackage-search.serokell.io/viewfile/transformers-compat-0.7.2/src/Control/Monad/Trans/Instances.hs#line-344) [https://hackage-search.serokell.io/viewfile/unpacked-these-0.1.0.0/src/Data/These/Unpacked.hs#line-343](https://hackage-search.serokell.io/viewfile/unpacked-these-0.1.0.0/src/Data/These/Unpacked.hs#line-343) [https://hackage-search.serokell.io/viewfile/validation-selective-0.1.0.2/src/Validation.hs#line-784](https://hackage-search.serokell.io/viewfile/validation-selective-0.1.0.2/src/Validation.hs#line-784)

There are four benefits of a migration towards removing second from Bifunctor that I can think of:

  1. Easier least effort instance definition due to a smaller minimal complete set. Facing the decision to either define bimap or both first and second most people currently choose to define bimap. Only defining first should suffice and first is strictly simpler than bimap. I am fairly certain that most/all instances that only define bimap would have benefitted from a smaller minimal set and thus I believe the vast majority of future non-derived Bifunctor instances will benefit from such a migration by only defining first (instead of bimap).
  2. Impossible to violate fmap = second.
  3. Beyond ruling out inconsistencies between fmap and second (see benefit 2) removing (or in the future avoiding) the code for the redundant definition of second eliminates code that could contain errors. Even the canonical definition second = fmap is likely simpler/no worse than any other definition of second. Keep in mind that there is only a small fraction of instances that define second but do not define it as second = fmap. Additionally this is not strictly beneficial for current noncanonical definitions of second, because there are migration costs.
  4. A smaller class dictionary.
    All instances including derived ones benefit from this.

I like benefit 1 a lot, because it simplifies so many future instances. In contrast benefit 3 applies to very few instances and I am unsure to what extent the decreased dictionary size from benefit 4 matters. Concerning benefit 2: I wonder how obvious/intuitive it is that implementors need not care about fmap = second, but still have to pay attention to other laws such as fmap = bimap id. Generally the documentation seems to be lacking, e.g. it requires bimap f g = first f . second g, but does not clarify whether bimap f g = second f . first g should also hold.

Note that we can alternatively obtain benefit 1 by shrinking the complete-set without removing second. This is what IcelandJack proposed initially.

I see the following migration path(s):

  1. Add Functor as a superclass of Bifunctor. We could leave it at that. If we opt to go further, we add a -Wnoncanonical-bifunctor-instances warning, which is enabled by default.
  2. Wait a few (3?) GHC releases.
  3. Remove second from the minimal complete set of Bifunctor and change the default definition of second from bimap id to fmap. We could leave it at that. If we opt to go further we additionally replace the -Wnoncanonical-bifunctor-instances warning by a warning that tells you to remove any definition of second.
  4. Wait a few (3?) GHC releases
  5. Move second out of the Bifunctor class.
How far Up to step Number of edits required on Hackage
Only add Functor as a superclass 1 0
Remove second from the minimal complete set 3 66 = 52 + 14
Remove second from the Bifunctor class 5 152 = (52 + 14) + (34 + 52)

If we go all the way, then the (52) Bifunctor instances that are currently not canonical will be edited twice.

To reiterate: We can get away with relatively few edits compared to Monoid/Monad, because there are only very few definitions of second in the first place, since most instances only define bimap. Nonetheless it is a lot of work.

Bodigrim commented 1 year ago

Thanks for detailed impact analysis, that's very thorough.

The proper path to remove second is:

  1. CLC proposal to make Functor a super class for Bifunctor (we are here).
  2. GHC proposal to introduce -Wnoncanonical-bifunctor-instances, because introduction of new warnings is outside of CLC remit.
  3. CLC proposal to remove second from Bifunctor.

I'd suggest to stick to Step 1 only in this topic, otherwise the discussion will sidetrack pretty quickly. We can return to Step 3 once Step 2 is completed.

At the moment I personally lean against removing second from Bifunctor: in my opinion potential benefits are not sufficiently pronounced.

Topsii commented 1 year ago

We can do it step by step if you prefer that. Surely only a decision by the CLC can motivate a GHC proposal for the warning? But that can be done in another CLC proposal I guess.

You said

I don't see any specific obstacles to move the proposal forward.

I'd like to trigger the vote then.

Bodigrim commented 1 year ago

Dear CLC members, let's vote on the proposal to add a Functor superclass to Bifunctor:

-class Bifunctor p where
+class (forall a. Functor (p a)) => Bifunctor p where

The merge request is available at https://gitlab.haskell.org/ghc/ghc/-/merge_requests/9313/diffs. It does not change the default definition of second and does not shrink {-# MINIMAL #-} set of definitions.

The impact analysis can be found at https://github.com/haskell/core-libraries-committee/issues/91#issuecomment-1278299233. The proposer has raised PRs to pretty much all affected packages, adding instance Functor (T a) for each T such that instance Bifunctor T is defined. This is a straightforward and backward-compatible fix.

@tomjaguarpaw @chessai @emilypi @cgibbard @mixphix

+1 from me. I think this change fits nicely into other recent developments wrt quantified superclasses.

tomjaguarpaw commented 1 year ago

EDIT: I changed my vote.

Original message

-1

This proposal is technically a good one. My -1 is not a response to this proposal in particular, but to Bifunctor in general, which I don't think we should perpetuate by trying to improve it.

My objection to Bifunctor in general is that behaviour that is based on the accident of type parameter ordering seems far too fragile. Besides, where are we going to stop? Trifunctor, Quadrafunctor? Functor is a necessity for several reasons, and remains within the realm of the manageable because it only refers to a single type parameter, and so many useful instances only have a single parameter anyway. I would always rather see over _Left f and over _Right g (or the equivalent for other data types) than first f and second g.

Ericson2314 commented 1 year ago

@tomjaguarpaw I am also confused why Bifunctor was added to base, but so long as it is there this design seems strictly better? I would advocate both for this change and removing it from base, do you see a contradiction between those?

emilypi commented 1 year ago

+1

While I do think there are better abstractions, like the FunctorOf work that @Icelandjack has been working on, I'd rather not let better be the enemy of good; we should improve the existing bifunctor so that we can unblock the addition of Profunctor in base, which will significantly deduplicate many repeated parts of the optics ecosystem. Later, if there are better paradigms, we can make the switch. This to me seems both minimally painful, and better bang for the buck than the competing ideas.

With competing ideas, we also have to consider that quite a bit of performance-sensitive code is written with the current Bifunctor/Profunctor split, particularly in lens. Any move towards better abstraction needs to preserve this, or sacrifice performance gains with a significantly better UX/DX so as to justify it. I'm not convinced it will. It seems more like it would just trigger a whole lot of work recalibrating what was already stable, as opposed to the change detailed in this issue, which should have minimal impact @tomjaguarpaw.

Ericson2314 commented 1 year ago

I would not want Profunctor in base, as I think moving things to base is generally terrible and results in precisely these ossification problems, but on the bigger picture of avoiding perfect as enemy of good I agree entirely.

Icelandjack commented 1 year ago

@emilypi Adding the superclass also gives a path to evolve Bifunctor to a FunctorOf representation. The goal of FunctorOf is to provide a shared functorial interface and eliminating the need for defining a separate class for each point in the hierarchy. Nobody wants a standalone Trifunctor class.

tomjaguarpaw commented 1 year ago

Adding the superclass also gives a path to evolve Bifunctor to a FunctorOf representation

Can you explain how that would work? It's not clear to me what the superclass has to do with it.

Icelandjack commented 1 year ago

This is not official, only my personal roadmap. It depends on the ability to be able to define proper type class synonyms, which I think of in terms of class frontends and backends. (I will create a proposal on this)

The categorical functor provides an amazingly general interface. The problem is writing instances, we want to continue to use the Bifunctor interface for backward compatibility and simplicity.

-- frontend
instance Bifunctor (,) where
  first :: (a -> a') -> ((a, b) -> (a', b))
  first f (a, b) = (f a, b)

rather than exposing natural transformations to the users:

-- backend
instance Functor (,) where
  type Source (,) = (->)
  type Target (,) = Nat (->) (->)

  fmap :: (a -> a') -> Nat (->) (->) ((,) a) ((,) a')
  fmap f = Nat \(a, b) -> (f a, b)

The basic idea is to elaborate the former into the latter. A frontend don't exist as a class, it immediately elaborates into its backend. If two users define separate Trifunctor frontends they can interoperate because they are programming against the same interface. Any FunctorOf interface that is more general than Trifunctor compatible.

FunctorOf is a MPTC frontend for the categorical functor, and Prelude.Functor is a frontend for FunctorOf (->) (->).

type  FunctorOf :: Cat s -> Cat t -> (s -> t) -> Constraint
class frontend FunctorOf src tgt f where
  --  (eliding methods is a shorthand for when they are the same)
  -- fmap = fmap

  backend Category.Functor f where
    type Source f = src
    type Target f = tgt
    -- fmap = fmap

type  Functor :: (Type -> Type) -> Constraint
class frontend Functor f where
  backend FunctorOf (->) (->) f

The FunctorOf instance below is elaborated into the same Functor (,) instance as above:

instance FunctorOf (->) (Nat (->) (->)) (,) where
  fmap :: (a -> a') -> Nat (->) (->) ((,) a) ((,) a')
  fmap f = Nat \(a, b) -> (f a, b)

Now we can define Bifunctor as a frontend. @tomjaguarpaw: In order to construct the natural transformation between bi a and bi a' we must require that both of them are regular Haskell Functors (a frontend of FunctorOf (->) (->)). So in order to elaborate the Bifunctor bi frontend to the categorical functor we need some guarantee that bi a is a functor for all a. This is exactly why the quantified constraint is necessary because otherwise a Bifunctor class does not have enough information to be elaborated into a categorical functor.

type  Bifunctor :: (Type -> Type -> Type) -> Constraint
class frontend (forall a. Functor (bi a)) => Bifunctor bi where
  first :: (a -> a') -> (bi a b -> bi a' b)

  backend FunctorOf (->) (Nat (->) (->)) bi where
    fmap :: (a -> a') -> Nat (->) (->) (bi a) (bi a')
    fmap f = Nat (first f)

See the definition of Nat. 

type Nat :: Cat s -> Cat t -> Cat (s -> t)
data Nat src tgt f g where
  Nat :: (FunctorOf src tgt f, FunctorOf src tgt g)
      => (forall a. tgt (f a) (g a))
      -> Nat src tgt f g

This is a longshot but without this functionality I don't see any way to evolve our hierarchies. As an added bonus this separates the interface of a class from its machine representation so we can derive Traversable and every other type class you can think of! (see why this is a pain).

The same will be possible for Generic and Generic1 which face the same arbitrariness: why not Generic2.. etc.? Instead we introduce GenericK for arbitrary kinds as a backend for Generic and Generic1. Every existing instance continues to compile as usual.

Then a lot of other classes like Filterable can be elaborated into FunctorOf (Kleisli Maybe) (->) with a minor technicality that you need a newtype wrapper so it doesn't overlap with FunctorOf (->) (->) instances but this is a formality and will not be seen by the user.

Bodigrim commented 1 year ago

FWIW the proposal makes Bifunctor more restrictive than currently, which is a good thing even (and especially) if you do not like the class itself.

@cgibbard @chessai @mixphix this is a gentle reminder to vote.

chessai commented 1 year ago

+1

I also think it should be removed, but we should improve the quality of what is already present

tomjaguarpaw commented 1 year ago

+1

OK, I am persuaded to change my vote, if that is permitted. The notion of "bifunctor" is a perfectly coherent one, I just don't particularly like the current implementation (and better implementations seem somewhat elusive in the current type system of Haskell). This proposal actually improves the current implementation (although only a small amount) so perhaps best not to oppose it.

N.B. my feelings about Bifunctor, which I believe is an effort at an implementation of a coherent notion, are in contrast with my feelings about Foldable, which I believe isn't.

mixphix commented 1 year ago

+1, and thank you for the detailed explanation of FunctorOf @Icelandjack !

Bodigrim commented 1 year ago

This gives us 5 votes in favor out of possible 6, so the proposal is approved. Thanks all!

Bodigrim commented 1 year ago

@Topsii one last thing, could you please prepare a migration guide for this breaking change? You can probably use https://github.com/haskell/core-libraries-committee/blob/main/guides/functor-combinator-instances-and-class1s.md as a template.

Topsii commented 1 year ago

Blindly using that guide as a template it would suggest

If you defined instance Bifunctor Foo but omitted instance Functor (Foo a), you must now define the latter. You can do this with fmap = second.

We may not want this, because it undermines a removal of second.

Should the migration guide instead suggest to define second = fmap anticipating a future removal of second? Is the CLC in support of removing second from the minimal complete set? This removal of course requires that a noncanonical-bifunctor-instances warning has been approved by the GHC steering commitee, implemented and enabled by default in say at least 3 GHC releases. I am not proposing to remove second from the class only from the minimal set. Do you want me to open another issue for this?

Surely only a decision by the CLC can motivate a GHC proposal for the warning?

With the blessing of the CLC I would open a GHC proposal for the noncanonical-bifunctor-instances warning.

Ericson2314 commented 1 year ago

How do you feel about fmap = bimap id?