Adding `branch` to the class definition

[j-mie6]

The branch operation can be implemented efficiently on its own, and select can be efficiently implemented in terms of it. This is similar to Applicative's (<*>)/liftA2 for which a more efficient implementation may exist with one compared to the other. I propose doing something similar with Selective such that:

class Applicative f => Selective f where
    {-# MINIMAL (select | branch) #-}
    select :: f (Either a b) -> f (a -> b) -> f b
    select x y = branch x y (pure id)
    
    branch :: f (Either a b) -> f (a -> c) -> f (b -> c) -> f c
    branch x l r = select (select (fmap (fmap Left) x) (fmap (fmap Right) l)) r

At the very least, adding branch to the class would enable a more efficient definition to be given, even if the MINIMAL is not used.
This is done for Applicative with (*>), (<*); Alternative with many and some; Monad with (>>).

[snowleopard]

I've always wanted to add branch to Selective but there are a few details that need to be worked out:

• Firstly, branch is more expressive than select. It allows one to express mutual exclusion between the two branches, which is something that can't be expressed with select. That is, if you statically analyse the default implementation of branch via two selects, you'd think that both branches can fire.
• Secondly, what laws should we add to relate select and branch? Some are trivial (like the interaction of branch with pure) but others are less so (like how does selects associativity interact with branch?).
• Finally, if you add branch to Selective, (some) existing free constructions will cease to be free, so new ones will need to be added. Because branch is more expressive, we'll most likely lose the nice list-like free construction available for select-only selective functors.

I think the comparison with Applicative and friends is not quite right because branch can't really be expressed via select, unless we somehow make it as expressive as select via a clever choice of laws, that, for example, would make it illegal to observe mutual exclusion.

[snowleopard]

unless we somehow make it as expressive as select via a clever choice of laws, that, for example, would make it illegal to observe mutual exclusion.

This set of laws probably doesn't need to be clever. Here is a pretty dumb law that makes branch as expressive that select:

• branch x l r = select (select (fmap (fmap Left) x) (fmap (fmap Right) l)) r

:)

But it feels so unsatisfactory!

[j-mie6]

I see. I'm actually of the mind that the greater expressive power is nice: is there any reason why we wouldn't want that? I suppose it would make the case that branch cannot be defaultly implemented with select because then that would alter it's expressivity, but I'm not convinced about that.

Do we know what the free construction would look like with Branch?

Personally, anything I've done with Selectives so far has been without using the class (for reasons), so I've always favoured branch as the default. I'm trying to think whether any analysis I've done wrt branch has relied on the mutual-exclusion or not...

[snowleopard]

I'm actually of the mind that the greater expressive power is nice: is there any reason why we wouldn't want that?

There is no particularly good reason. I was initially interested in studying the simplest possible primitive, which comes in the form of select that nicely fits into the family of binary operators like <*> and >>=. With branch, we gain expressivity and make the construction more pleasingly symmetric, but we do lose some of the simplicity/minimality. I think both select-based and branch-based definitions are interesting (plus, there are a few others like biselect and friends).

Do we know what the free construction would look like with Branch?

That would depend on the set of laws. If we include the following pretty natural law

• Associativity (unsure about the name): branch x f g = branch (swapEither <$> x) g f

then we'll be able to reassociate all branching expressions into lists, much like we do with selects.

That is any expression could be rewritten into branch x f (branch y g (branch z h ... )).

[j-mie6]

I think it's possibly better called commutativity? Yes, this is one law I have listed down for branch in my PhD thesis.

[j-mie6]

I think it is probably the case that there are no examples of Selective functors that cannot implement branch with the property we want right?

[snowleopard]

Yes, "commutativity" (of branch _ viewed as a binary operator) seems good to me, let's use this name.

I think it is probably the case that there are no examples of Selective functors that cannot implement branch with the property we want right?

There are no select laws that allow you to commute effects, so in (select-only) free selective functors the commutativity law won't hold. You won't be able to rewrite ... x ... f ... g into ... x ... g ... f because that does fundamentally rely on mutual exclusion of f and g, unless the underlying functor is itself commutative (but we don't want to assume that).

[j-mie6]

I meant more are there any existing instances that couldn't be commutative, I guess?

[snowleopard]

Sure, any free selective functor. It's an instance of the class after all :)

For example: https://github.com/snowleopard/selective/blob/main/src/Control/Selective/Rigid/Free.hs

[j-mie6]

And also any select that executes both branches too (with select = selectA)

[snowleopard]

And also any select that executes both branches too (with select = selectA)

That doesn't seem right to me. For example, Over (which uses select = selectA) can be commutative as long as the monoid used for accumulating effects is commutative. Say, if you'd like to count the number of effects in a selective/branching computation, you can easily do that in a commutative way with selectA.

[j-mie6]

Ah, fair. Yes I was thinking about Applicatives where the order of effects matters

More precisely then, it doesn't work for select = selectA when (<*>) doesn't "commute", i.e. where (<**>) /= flip (<*>)

[j-mie6]

If you think it's worthwhile, I could probably dedicate some "tube time" to thinking about laws that might involve select and commutative branch's interactions?

[snowleopard]

That sounds good, thanks!

Here is one possible plan that seems to work:

• Add branch to Selective but don't provide a default implementation because it won't satisfy the commutativity law in general. And I think we really want the commutativity law.
• Provide a default implementation for select: select x y = branch x y (pure id). In this way, it's still sufficient to define only one method when declaring a class instance: it's just going to be branch instead of select.
• Come up with a set of laws just for branch. I think that's relatively straightforward: in addition to commutativity, we want generalised versions of select's identity, distributivity and selectM laws.
• Prove that the old select laws follow from the new branch laws.
• Come up with a free construction. I think I have some drafts for this somewhere.

It's sad that this plan involves breaking all users of the library (they'll have to redefine their instances via branch instead of select) but that shouldn't be too painful.

[j-mie6]

yeah, the break is annoying. If only Haskell had a rewrite tool for stuff like this (Scala has scalafix, which can be used for migrating to new breaking versions of libraries or compiler, for instance).

One helpful mitigation would be putting in branchS, which would be the current implementation of branch, for a quick branch = branchS to keep the compiler happy.