WIP: Selective

[rossabaker]

Experimental, incomplete integration of Selective into the hierarchy.

See #2745

[rossabaker]

I thought this would get stopped cold by binary compatibility and only expected to spend a few minutes on this. Alas, it seems to work. I'll pause here and see if anyone thinks this approach is fruitful.

/cc @cb372 @hamishdickson whose prior art can be spliced in here if we proceed.

/cc @LukaJCB @johnynek who both showed interest in the original.

[codecov-io]

Codecov Report

Merging #3709 (dba3dc0) into master (7fd119d) will decrease coverage by 0.21%. The diff coverage is 72.59%.

@@            Coverage Diff             @@
##           master    #3709      +/-   ##
==========================================
- Coverage   90.24%   90.02%   -0.22%     
==========================================
  Files         391      397       +6     
  Lines        8863     8975     +112     
  Branches      227      251      +24     
==========================================
+ Hits         7998     8080      +82     
- Misses        865      895      +30     

[johnynek]

Here is an idea we can experiment with here: for every function on the typeclass we add a law that it behaves the same as the default. This allows us to override fearlessly and know that if the laws pass it must be correct.

[rossabaker]

The Haskell implementation introduces an operator for select: <*?. Should we?

[rossabaker]

Nope, that last commit is bad. My solution was dubious, and I failed to test the rigid laws.

[j-mie6]

Wanted to weigh in on this (a bit late, I know!): I'd like to point out that branch might be a better abstract operation to support than select:

• branch[A, B, C](mx: F[Either[A, B]])(left: F[A => C], right: F[B => C]): F[C] (shuffle the currying around to taste) is nice because it can implement select using one operation (and it's as easy as branch[A, B, B](mx)(my, identity[B].pure). The inverse direction requires two selects
• branch very obviously corresponds to a lifted fold on Either (or in other words a lifted pattern match), whereas selects high-level idea is less immediately obvious. This is a nice symmetry with <*> being a basic lifted function application and flatMap being a lifted variable-binding.
• The selective laws apply similarly to branch with a couple of intuitive modifications.
• branch was also presented in the original selective paper (although they picked select for nicer associativity laws, if I recall correctly, it's been a while)

Also I believe that there are some nice interactions between select and failure for an Alternative. Having both Alternative and Selective gives you access to a filter combinator, as well.

[rossabaker]

I'm unsure at this point whether it's easier to scrape the bitrot off this PR or start over and hope to not reopen the same issues that we did manage to work through here, but I'm interested in trying or handing the baton to someone else.