Please add 'f a -> f a -> f a' to signature for Divisible

[tomjaguarpaw]

divide (\x -> (x, x)) :: Divisible f => f a -> f a -> f a is equivalent to divide :: (a -> (b, c)) -> f b -> f c -> f a and surely more convenient. Could it be added to the typeclass signature?

[sjoerdvisscher]

This makes me wonder if Divisible is actually more like Alternative, and Decidable more like Applicative. Which wouldn't matter much except that Divisible is now a superclass of Decidable, and maybe that should be the other way around?

[tomjaguarpaw]

Let's look at how these classes treat products:

• Applicative: (f a, f b) -> f (a, b)

• Alternative: (f a, f b) -> f (Either a b)

• Divisible: (f a, f b) -> f (a, b)

• Decidable: (f a, f b) -> f (Either a b)

From this angle Divisible looks like Applicative.

[sjoerdvisscher]

Yes, but we're going from covariance to contravariance, so I would actually expect that product and coproduct switch roles.

[ekmett]

I don't have this paged in to my working memory well enough to refute that categorically, but I can argue that pragmatically, the hierarchy running the other way is rather less useful. Far more things can handle 'lots of products and fixed shape' than '1 choice out of a bunch of alternatives' that you might write with generics. In everything I've written using the origin of these abstractions the sum case is the thing that needed something 'extra'. Sort of the difference between applicative and monad: The product case usually doesn't have to branch or choose what to do, just plumb stuff around and combine it. The sum case needs to make decisions.

If we assume we're playing with (right)(semi)(near)rings and what have you the distributive laws also look like the usual direction, they don't flip either. So I think something is off in your intuition in this case.

That said, you might argue that the sum case only has to make decisions it doesn't have to deal with combining anything.

[Zemyla]

Best argument for switching them: Divisible (Op r) requires Monoid r, but Decidable (Op r) really shouldn't.

[ekmett]

That would be an example of the sum case that only has to make decisions and not combine.

But then you can make the exact same argument about Alternative not needing Applicative as a superclass as there are plenty of functors for which a FunctorPlus would be available, but not Applicative. The problem then is that the operations you'd get from such a class don't have any natural distributive law in relation to the ones in Applicative (ignoring the fact that even Applicative/Alternative have one of 2-3 different sets of laws!). This would mean you'd really need three classes. A sum-based ContravariantPlus, a product based Divisible. and a Decidable that promoted the choose/lose to have at least the loose distributive laws that applicative/alternative have.

I chose to forego the ContravariantPlus level of abstraction simply because of a lack of good usecases, and for symmetry with the other side. Similarly Comonad avoids introducing Semicomonad, because the asymmetry with Monad creates pain points for duality.

[ekmett]

You'd also need separate names for the Decidable combinators vs. the ContravariantPlus ones, for type inference reasons, lest you wind up with a bunch of code with lawless interactions between ContravariantPlus and Divisible, so restructuring this way isn't without a cost.

[ekmett]

To the original topic here, such a divide violates the "linear" intuition about how such predicates decompose. There is a real downside to it as well, consider using the variant form of divide proposed over and over recursively, to say divide out and handle separately everything element in a list (with the help of decidable for list length). You then have to contramap in the walk down the list at each step reverting this to the previous form with multiple passes or else you pay O(n^2) in the list length because each decision is doing its own (tail . tail . tail ....). It was this observation of different asymptotics in Fritz Henglein's papers on discrimination which led me to select the current, safer API, which causes you to map at an earlier point.

I'm not terribly averse to adding a stylized divide0 or something as a member, but instances that implement just this method will be slower for almost every actual usecase I have involving these classes because they'll have to contramap in a separate pass for the current divide, so I'd rather have it as just a combinator that uses the class if we do decide to add it.

[tomjaguarpaw]

such a divide violates the "linear" intuition about how such predicates decompose

I don't understand that. Could you explain? I've found it very natural in practice.

Fair enough about the efficiency concerns though. I've never considered them.

[ekmett]

If you look at the way all the generic instances for these work they break apart the sums and products and do things with both sides. Not everything will behave that way obviously if you program with these combinators directly, but the intuition does help guide the api design. The efficiency concern was really the thing front and center in my mind when writing the code, though.