Consider incorporating Selective functor

[sideeffffect]

There's a new kid on the block: Selective functor, a sub-class of Applicative and super-class of Monad in the traditional hierarchy. It is special by having a method select: f (Either a b) -> f (a -> b) -> f b that can have both an

• Applicative interpretation (susceptible to inspection, but runs both effects) or the
• Monad interpretation (runs only the first effect, if it turns out that the content is Right b, but can't be inspected).

It's been

• introduced in Selective applicative functors, Mokhov et al., 2019
• suggested for cats
• implemented in cats-selective
• used in sbt

The laws are

-- Identity
x <*? pure id = either id id <$> x

-- Distributivity; note that y and z have the same type f (a -> b)
pure x <*? (y *> z) = (pure x <*? y) *> (pure x <*? z)

-- Associativity
x <*? (y <*? z) = (f <$> x) <*? (g <$> y) <*? (h <$> z)
  where f x = Right <$> x
        g y = \a -> bimap (,a) ($a) y
        h z = uncurry z

Would an abstraction like this make sense in ZIO Prelude? How should it look like to look the ZIO Prelude native way?

We may rather want to use as base the function branch: Selectivef => f (Either a b) -> f (a -> c) -> f (b -> c) -> f c

[jdegoes]

I don't think this is really necessary, since ZIO Prelude can directly encode introspectable monads, which generalize selective functors.

[sideeffffect]

Those are good news :+1: Less code to write and maintain :laughing:

How would we do it in ZIO Prelude then? :thinking:

[quelgar]

I find the idea of an introspectable monad very interesting, so I had a go at it myself. When googling, I found a gist from John, and yeah it looks like the way to do this is to restrict the types supported such that they have a “finite” (really, this means quite small) number of possible values. For example, the following defines a type Op with a flatMap which can be introspected because it’s restricted to only mapping from enumerable values:

import zio.prelude.*
import zio.Chunk

trait Enumerable[A]:
  def enumerate: Chunk[A]

object Enumerable:
  def apply[A](as: A*): Enumerable[A] = fromIterable(as)

  def fromIterable[A](as: Iterable[A]): Enumerable[A] =
    new Enumerable[A]:
      val enumerate: Chunk[A] = Chunk.fromIterable(as)

  given Enumerable[Boolean] with
    def enumerate: Chunk[Boolean] = Chunk(false, true)

  given Enumerable[Unit] with
    def enumerate: Chunk[Unit] = Chunk(())

  given Enumerable[Nothing] with
    def enumerate: Chunk[Nothing] = Chunk.empty

  given [A: Enumerable, B: Enumerable]: Enumerable[(A, B)] with
    def enumerate: Chunk[(A, B)] =
      for
        a <- summon[Enumerable[A]].enumerate
        b <- summon[Enumerable[B]].enumerate
      yield (a, b)

enum Flavour:
  case Chocolate, Strawberry, Vanilla

given Enumerable[Flavour] with
  import Flavour.*
  def enumerate: Chunk[Flavour] = Chunk(Chocolate, Strawberry, Vanilla)

// a monad for enumerable types
enum Op[+A: Enumerable]:

  case FlatMapFinite[A, +B: Enumerable](
      first: Op[A],
      values: Chunk[A],
      f: A => Op[B]
  ) extends Op[B]
  case MapOp[A, +B: Enumerable](first: Op[A], f: A => B) extends Op[B]
  case QueryFlavour extends Op[Flavour]
  case PrintLine(s: String) extends Op[Unit]
  case NoOp extends Op[Unit]
  case Succeed[+A: Enumerable](value: A) extends Op[A]

  def flatMap[B](f: A => Op[B])(using Enumerable[B]): Op[B] =
    FlatMapFinite(
      this,
      summon[Enumerable[A]].enumerate,
      f
    )

  def map[B](f: A => B)(using Enumerable[B]): Op[B] =
    MapOp(this, f)

  def prettyPrint: String =
    final case class Log(indent: Int, output: Chunk[String], eol: Boolean)
    def print(s: String) = State.update { (l: Log) =>
      val eolString = if l.eol then "\n" else ""
      l.copy(output = l.output :+ s :+ eolString)
    }
    def printIndent = State.update((l: Log) =>
      l.copy(output = l.output :+ Chunk.fill(l.indent)(' ').mkString)
    )
    def indent = State.update((l: Log) => l.copy(indent = l.indent + 4))
    def outdent = State.update((l: Log) => l.copy(indent = l.indent - 4))
    def cont = State.update((_: Log).copy(eol = false))
    def done =
      State.update((l: Log) => l.copy(eol = true, output = l.output :+ "\n"))
    def help[A](op: Op[A]): State[Log, Unit] = op match
      case QueryFlavour =>
        printIndent *> print("[QueryFlavour]")
      case Succeed(a) =>
        printIndent *> print(s"[Succeed $a]")
      case FlatMapFinite(first, values, f) =>
        help(first) *> {
          values match
            case Chunk(a) =>
              help(f(a))
            case as =>
              as.forEach_(a =>
                printIndent *> print(s"➥ $a") *> indent *> help(
                  f(a)
                ) *> outdent
              )
        }
      case MapOp(first, f) =>
        cont *>
          printIndent *>
          print("➠ ") *>
          done *>
          indent *>
          help(first) *>
          outdent
      case PrintLine(s) =>
        printIndent *> print(s"[Print \"$s\"]")
      case NoOp =>
        State.unit
    val workflow = help(this)
    workflow
      .runState(Log(indent = 0, output = Chunk.empty, eol = true))
      .output
      .mkString
end Op

The next question is how to define the zio-prelude typeclasses. The standard Covariant and AssociativeFlatten type classes have to be universal, I can't see a way to make them work with the above flatMap that has the Enumerable requirement.

However, there’s also CovariantSubset which can be defined for only a subset of values, and that works:

given CovariantSubset[Op, Enumerable] with
  def mapSubset[A, B: Enumerable](f: A => B): Op[A] => Op[B] = _.map(f)

But we need flattening also, and as of RC16 there’s no AssociativeFlattenSubset. It's possible to write such a typeclass, but I wasn't able to come up with a useful instance of it. The problem I couldn't get around is a requirement for a Subset[F[A]], and I couldn't find a good way to provide that.

Encoding the flattening via flatMap only requires Subset[A] though, so this works:

trait MonadSubset[F[+_], Subset[_]] extends CovariantSubset[F, Subset]:
  def flatMapSubset[A, B: Subset](f: A => F[B]): F[A] => F[B]
  def pureSubset[A: Subset](a: A): F[A]

extension [F[+_], A](fa: F[A])

  def *>[Subset[_], B](fb: F[B])(using monad: MonadSubset[F, Subset])(using
      Subset[B]
  ): F[B] = monad.flatMapSubset(_ => fb).apply(fa)

  def as[Subset[_], B](b: B)(using monad: MonadSubset[F, Subset])(using
      Subset[B]
  ): F[B] = fa *> monad.pureSubset(b)

given MonadSubset[Op, Enumerable] with
  def mapSubset[A, B: Enumerable](f: A => B): Op[A] => Op[B] = _.map(f)
  def flatMapSubset[A, B: Enumerable](f: A => Op[B]): Op[A] => Op[B] = _.flatMap(f)
  def pureSubset[A: Enumerable](a: A): Op[A] = Succeed(a)

Perhaps the usual identity of flatten(map(f)) ≡ flatMap(f) doesn't hold when we restrict to subsets?

Then we can write a program using Op and introspect it:

val workflow = Op.PrintLine("Which flavour?") *>
  Op.QueryFlavour.flatMap { flavour =>
    Op.PrintLine(s"Query result = $flavour") *> {
      flavour match
        case Flavour.Chocolate =>
          Op.PrintLine("Gimme chocolate").as(false)
        case Flavour.Strawberry =>
          Op.PrintLine("Everyone likes strawberries").as(false)
        case Flavour.Vanilla =>
          Op.PrintLine("Second flavour?") *>
            Op.QueryFlavour.flatMap { flavour2 =>
              if flavour2 == Flavour.Vanilla then
                Op.PrintLine("All vanilla").as(false)
              else Op.PrintLine(s"$flavour mixed with $flavour2").as(true)
            }
    }
  }

val s = workflow.prettyPrint
println(s)

output:

[Print "Which flavour?"]
[QueryFlavour]
➥ Chocolate
    [Print "Query result = Chocolate"]
    [Print "Gimme chocolate"]
    [Succeed false]
➥ Strawberry
    [Print "Query result = Strawberry"]
    [Print "Everyone likes strawberries"]
    [Succeed false]
➥ Vanilla
    [Print "Query result = Vanilla"]
    [Print "Second flavour?"]
    [QueryFlavour]
    ➥ Chocolate
        [Print "Vanilla mixed with Chocolate"]
        [Succeed true]
    ➥ Strawberry
        [Print "Vanilla mixed with Strawberry"]
        [Succeed true]
    ➥ Vanilla
        [Print "All vanilla"]
        [Succeed false]