add Selective

[johnynek]

https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors.pdf

trait Selective[F[_]]  {
  def applicative: Applicative[F] // we could also extend, but that may create ambiguities
  // the law here is if you give `F[Right[B]` we never evaluate `fn`
  def select[A, B](fab: F[Either[A, B]])(fn: F[A => B]): F[B]
}

object Selective {
  def fromMonad[F[_]: Monad]: Selective[F] =
    new Selective[F] {
      def applicative = Monad[F]
      def select[A, B](fa: F[Either[A, B]])(fn: F[A => B]): F[B] =
        fa.flatMap {
          case Right(b) => Monad[F].pure(b)
          case Left(a) => fn.map(_(a))
        }
    }
}

Note the paper gives some interesting examples of things that don't have Monad but do have Selective, e.g. Validated.

[LukaJCB]

I think Selective is super interesting and I can't wait to dive into it more fully.
I also think we could benefit from a more "Scala-like" encoding, as the one in paper is based on ap which is hardly used in Scala, due to no auto-currying. I envisioned something like

trait Selective[F[_]] extends Apply[F] {
  def selective[A, B, C](feab: F[Either[A, B]])(fc: F[C]): F[Either[(A, C), B]]
  def select[A, B](feab: F[Either[A, B]])(ff: F[A => B]): F[B] =
    map(selective(feab)(ff))(_.fold({ case (a, f) => f(a) }, identity))
}

modulo the inheritance bit.
I think this signature is equal in power, but doesn't involve any function application and is therefore a bit more verbose.
It'd also be really interesting if we could extract something like Semigroupal that is just the least powered version of this abstraction :)

[cb372]

I'm planning to take a stab at this today based on @johnynek's formulation. Can't guarantee I will get anywhere with it though.

[LukaJCB]

Not to discourage you @cb372, but I think it's a good idea to take our time and be patient with this. It's a very new and experimental abstraction, that could probably use some time discussing how to implement it, especially with how it fits in the cats hierarchy :)
Cats is supposed to be super stable, so anything that goes has to be "future-proofed" to some degree. With that said, I really appreciate you taking the time for this and I'm very much looking forward to see some of your conclusions :)

In other news, I'm super excited for this, the paper is really awesome, and I can some really cool things happening in this space in the future 🎉

[johnynek]

One idea might be to add some of the more interesting selective functions to Validated to see if we think those are useful.

Then consider are there interesting cases we care about beyond Validated.

[cb372]

@LukaJCB How would you like to proceed with this? We can hold off on doing any more work on that PR, if you want some time to explore other designs. Hopefully the PR is at least useful as a reference/proof of concept even if it doesn't end up getting merged.

/cc @hamishdickson

[hamishdickson]

@cb372 that definitely sounds sensible, there's definitely a bit of discussion around the implementation that needs to be had - especially around the hierarchy

BTW @LukaJCB we didn't see your reply until we were very deep down the rabbit hole!

[johnynek]

One way to make the member Applicative more ergonomic would be to add an implicit:

implicit def applicativeFromSelective[F[_]](implicit F: Selective[F]): Applicative[F]

Which we you can import or possibly be a low priority on Applicative if we can do it in a binary compatible way.

[LukaJCB]

I very much appreciate the PR, it's really great work!
I don't know if I'll personally have a lot of time to experiment in the near future, but to me, Selective seems huge. It's definitely an abstraction I've always wanted, seeing as monads IMO are way too strong and applicatives are too weak. I'm wondering if we've got the ergonomics figured it. I think as is, it might be a little awkward to use, though again, I haven't had the time to use it much.
I think one thing we could probably easily do is create a version that extends from Apply, so without pure.

Maybe it might make sense to think about a separate module for now? So that people can use it in their projects and experiment? I think it's not unreasonable to expect us to want to change something about any Selective implementation in 6-12 months, after the abstraction becomes more widely known and thus more widely used. What do you think @cb372 and @hamishdickson? :)

[hamishdickson]

That definitely sounds like a good solution about the separate module @LukaJCB - are you thinking some kind of experimental module? or literally just selective (I guess a bit like free)?

I think one thing we could probably easily do is create a version that extends from Apply, so without pure.

I think I'm missing something here - the laws and some of the combinators in the paper require pure - do you think there's a way to not use pure here?

It's a great abstraction - I'm really looking forward to seeing what people build with it! :)

[LukaJCB]

I think we could express associatvity and distributivity without pure, as well as a handful of combinators :)

[LukaJCB]

Another thing worth discussing; should the second argument be strict, by-name or use Eval one prevalent use case in the paper is use of selective parsers, where laziness can be quite important

Edit: if we look at precedence, all of ifM, whileM and friends use a by-name parameter, so I think we should probably use that as well, WDYT?

[LukaJCB]

I think we should set up a new repo cats-selective that contains the code for this for now, where we can easily create changes, and once we feel it's ready, we'll merge it into cats-core :)

[LukaJCB]

I have thought of a yet another thing we need to consider, what about the Parallel type class? Right now it represents going from a Monad to an Applicative, but I do wonder if it could be from Selective to Applicative instead 🤔

[johnynek]

@LukaJCB doesn’t that defeat the purpose of Parallel. We want to go from Either to Validated or IO to IO.Par. Cases like that are the motivation of the typeclass.

Also, in what cases are Selective map2 not what Applicative map2 would want? In IO and Validated map2 is not Parallel of course.

[cb372]

I'll try and set up a new cats-selective repo in the next few days, based on the code in the PR.

I'm still not sure about @LukaJCB's idea of extending Apply instead of Applicative. Sure, we could probably work around the lack of pure for most of the combinators, but I'm struggling to see the benefit. It feels a bit masochistic.

[LukaJCB]

@cb372 I'm sorry if I created confusion, I just said I want to split up Selective into two classes, one extending Apply and another Applicative. Similar to how we have FlatMap and Monad today :)

[cb372]

Ah ok that makes more sense 😄

[LukaJCB]

@johnynek, I guess you're right since there is no apS = ap law. Not sure if that means that it never makes sense, but I can't think of a situation right now.

[LukaJCB]

So what if I want to have a statically analyzable IO, it'd be nice to be able to express the difference between what is now *> and &> or mapN and parMapN. I could make mapN parallel by default for such a data type, but then I have to express any Applicative combinator I want to use in sequence with select. I think for a type like this, the problem that Parallel tries to solve remains, namely having two distinct applicative instances where one is a dependent computation and the other an independent one. I'm not quite sure what the implications are. I think the easiest would be to try it out and experiment :)

[cb372]

I've set up https://github.com/cb372/cats-selective (just in time before @LukaJCB explodes with excitement, based on his recent Twitter output)

It's still very bare-bones, pretty much the code that was in the PR, but it should be a good base for experimentation. I'm happy to transfer it to typelevel or leave it where it is.

Currently it's missing a licence. Is there a recommendation here? I see cats-tagless is Apache 2.0 but cats-mtl has a COPYING file.

[snowleopard]

I guess you're right since there is no apS = ap law.

@LukaJCB This property does hold for many selective functors, and we call such selective functors "rigid" in the paper. For example, all monads are rigid because apS = ap follows from select = selectM. You probably know this already but I thought it's worth mentioning just in case.

[LukaJCB]

@cb372 I think mirroring Cats' usage of MIT license is probably easiest :)

[kailuowang]

@cb372 , this is awesome. Do you plan to release it to maven central through sonatype? Another option is to resurrect the idea of a cats. experiment module inside the main repo for such small but experimental things. WDYT @LukaJCB

On a side note, cats-tagless license is inherited from Mainecoon but I think we should conform to Cats' MIT license.

[cb372]

OK I'll put an MIT licence on it 👍

Sure, I can set up sonatype publishing when necessary. I'll have to change the organisation to my own com.github.cb372 though.

[milessabin]

I found myself in need of this recently. It'd be great if we could move this forward in cats.

[rossabaker]

Here's a real-world, open-source Selective use case: typelevel/cats-parse#101

[johnynek]

I think it is pretty clear that Selective is as useful as many of the typeclasses in cats.

One thing I would vote for: I don't see the value in making a default implementation from Selective using Apply. If you don't get laziness in the second parameter, I don't see a big win of Selective and would rather encode such eager methods directly on Apply.

I think the paper calls these "tight". I think we should have the laws require tightness.