snowleopard/selective

Examples of Non-Selective

Closed this issue · 19 comments

ulysses4ever commented

Hello Andrey! I thought you might be willing to think about examples of non-selective functors and selective functors which are not monads (as in this SO thread on non-examples of other CT-structures, much in the spirit of Gelbaum and Olmsted's Counterexamples in Analysis). I'm not quite sure about the first part (non-selective applicatives) given that you can always build selectA but it is worst discussing still, I guess.

snowleopard commented

Hello Artem! Thanks for the question -- it's useful to practice answering it, since I'm writing a paper about selective functors right now :)

Every applicative functor is selective in its own peculiar way. Indeed the definition select = selectA gives you a perfectly lawful Selective, although perhaps one might argue that it is entirely "non-selective".

In other words, the abstraction I have does not allow you to distinguish "0.0 selectivity" of selectA, from "1.0 selectivity" of selectM at the type level. (Or from, "0.5 selectivity" of applicative functors that exist in between. One might even say that functors like Under have negative selectivity!)

The reason the new abstraction is useful, is because it gives you vocabulary to talk about selectivity, and a way to explicitly make use of selectivity by calling the method select in a Selective context.

One might argue that the select method should simply be added to the Applicative type class, with the default implementation select = selectA. This is indeed a viable approach, but it has two drawbacks: (i) this is a breaking change, since the new method will conflict with any existing definitions of select, and (ii) more importantly, it will make it harder to reason about code with the Applicative f constraint, since the new method will make it possible for "new applicative" effects to be dependent (i.e. it will become possible for effects to depend on values). This is why I think selective functors deserve a separate type class.

ulysses4ever commented

it's useful to practice answering it, since I'm writing a paper about selective functors right now :)

I noticed that that's why the question! :-)

I'm not really arguing about the usefulness of the abstraction itself or the design issues we can think of — both are described in good detail in your blog post. Instead, I'm saying that having concrete examples of non-selective things as well as selective-non-monadic things might be useful for the reader (of the paper). Like it is useful to know that there is no way we can turn (lawfully) data T a = T (a -> Int) into a functor, nor a functor data F x = F Void into an applicative (well, Pointed), etc.

snowleopard commented

Instead, I'm saying that having concrete examples of non-selective things as well as selective-non-monadic things might be useful for the reader

It might, but I'm afraid I don't understand what exactly you mean by "non-selective" and "selective-non-monadic things". Could you make the question a bit more precise?

Is Over "non-selective"? What about Under?

If they are both selective (they are instances of Selective after all!), then by "non-selective" you might mean "non-applicative", in which case the separation is already known, e.g. your data F x = F Void.

Then what about "selective-non-monadic things"? If you are talking about all functors having a Selective instance but not a Monad instance, then this boundary coincides with the Applicative/Monad boundary, and both Over and Under are examples of such "selective-non-monadic things".

ulysses4ever commented

boundary coincides with the Applicative/Monad boundary

This answers my questions fully, thank you!

snowleopard commented

@ulysses4ever If you don't mind, I'd like to leave this open for some time, since I feel that the relationship between Applicative, Selective and Monad is still not quite clear (at least in my head).

For example, strangely, Selective is much closer to monads in power in the following sense.

Let's rewrite the combinator ifS :: f Bool -> f a -> f a -> f a as follows:

bindBool :: Selective f => f Bool -> (Bool -> f a) -> f a
bindBool x f = ifS x (f False) (f True)

So, we get a monadic bind specialised to Bool. But this doesn't stop here: it's not difficult to see that we can do the same with the 3-valued Ordering, although it's not pretty:

branch3 :: Selective f => f (Either a (Either b c)) -> f (a -> d) -> f (b -> d) -> f (c -> d) -> f d
branch3 x a b c = (fmap (fmap Left)     <$> x)
              <*? (fmap (Right . Right) <$> a)
              <*? (fmap Right           <$> b)
              <*? c

bindOrdering :: Selective f => f Ordering -> (Ordering -> f a) -> f a
bindOrdering x f = branch3 (toEither <$> x) (const <$> f LT) (const <$> f EQ) (const <$> f GT)
  where
    toEither LT = Left ()
    toEither EQ = Right (Left ())
    toEither GT = Right (Right ())

...then to Word8, or any other enumerable type, resulting in bindS:

bindS :: (Bounded a, Enum a, Eq a, Selective f) => f a -> (a -> f b) -> f b

Furthermore, if we change the definition of Selective in a way which allows a potentially infinite sum type to be inspected with a suitable select method, we get the full power of a monad!

@copumpkin demonstrated this surprising fact here:

https://gist.github.com/copumpkin/d5bdbc7afda54ff04049b6bdbcffb67e#file-selectivesigma-hs-L53-L58

To sum up, the boundary between Selective and Monad is an interesting one and worth thinking about.

ulysses4ever commented

Thanks! Sure, let's leave this open.

When opening this initially I wanted to point one thing. Understanding type classes can go through several paths (all of which are important, I think): interface, laws, instances. In the previous discussion, I missed the way of instances. After your remarks, I think that this way might be not that interesting for the case of Selective. In contrast, the way of interfaces is, indeed, seems to be full of surprises; in particular, interactions between the interface of a monad and that of a selective.

glaebhoerl commented

Other potentially-relevant prior discussion:

Apparently four years ago I already couldn't find where I'd originally encountered the "class Applicative f => Branching f" idea.

And this is something I just came across while googling for it.

  • 👍1
snowleopard commented

@glaebhoerl Nice, thank you!

It would be great if you could remember in which context you've seen Branching -- interestingly, I've also considered using it as a name of the type class.

Describing the link with ArrowChoice is on my todo list. It is definitely a solid alternative to this whole Selective business, but arrows have always felt too heavy to me personally. I'd like to argue that switching an existing codebase built on top of Applicative and Monad (which is quite common) to arrows is impractical, since everything will need to be reshaped into an arrow. On the other hand, adding a Selective instance is easy, and you immediately get to reuse some selective combinators.

snowleopard commented

Understanding type classes can go through several paths (all of which are important, I think): interface, laws, instances.

@ulysses4ever Very nice way of putting it! Indeed, selective functors are mostly interesting in terms of the interface and associated laws, while all instances remain good old Applicatives and Monads.

glaebhoerl commented

It would be great if you could remember in which context you've seen Branching

All I remember is:

  • It was a long time ago (apparently, >4 years, so probably at least 6)

  • On reddit

  • Somebody was asking if there's anything in between Monad and Applicative, and someone suggested maybe Branching with the m Bool method...

But no amount of googling/reddit-search has been able to locate it.

And maybe my memory is faulty -- maybe it wasn't reddit, but #haskell or haskell-cafe or...

  • 👍1
copumpkin commented
snowleopard commented

Thanks @copumpkin, I'll write to Brent!

mstksg commented

Would it maybe be more interesting to distinguish the cases where the Right effect is skipped, vs. the cases where the Right effect is taken?

From the original description, this seems like a powerful tool for static analysis that distinguishes it from Applicative -- the fact that you must skip the Right action. This gives us some interesting results, I think.

For example, this gives an answer to @ulysses4ever original question: Const becomes an example of something that cannot have such an instance. So Const becomes a "Non-Selective". You also now get the "strict subclass" dichotomy: all Selective are Applicative, but not all Applicative are Selective. It's a clearer hierarchy.

It becomes interesting because a lot of times in Haskell, abstracts take their character from what types can't fulfill them...not what types can. You get as much benefit from excluding a type as you do from including it. If the "can/can't" overlaps perfectly with Applicative then it's at risk of losing a bit of its character, maybe?

Though at the top level, you might want to generalize the definition to include all "degrees of selectiveness", if you split it up into two typeclasses, it can help you classify different levels and have a more explicit hierarchy?

snowleopard commented

@mstksg I think it is useful to leave selective functors under-specified in the same way as applicative functors are left under-specified.

In Applicative, there is no law on the order in which computations are executed. Left to right, right to left, in parallel – all these options are fine according to the type class laws. And this makes it possible for some instances (e.g. Const) to execute applicative computations in sequence from left to right, while other instances, like Haxl execute applicative computations in parallel. And this is great!

Note that as soon as we also have a Monad, we gain an additional requirement (<*>) = ap, which tells us that, at the semantic level, the result should be as if the effects were executed in sequence from left to right.

We have a pretty similar situation with Selective: we under-specify the behaviour at first, i.e. allow every instance to choose whether whether to skip the unnecessary effect (to save work) or execute it (to record as part of static analysis). But then again, Monad comes with an additional requirement select = selectM, which dictates that unnecessary effects must be skipped.

Does this make sense? As far as I can see, if add any law on the unnecessary effect, we will lose the ability to write a selective expression once, and then interpret it in different contexts depending on our current needs (i.e. static analysis vs execution).

snowleopard commented

Putting the above argument in the paper, as we speak :)

laws

simonmar commented
snowleopard commented

@simonmar True. Perhaps, I could replace Haxl with Concurrently from Control.Concurrent.Async here, which is no longer a monad?

snowleopard commented

OK, I think we can now close this. I did my best to answer all questions about the relative power of applicative functors, selective functors and monads in the paper:

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

Of course, everyone should feel free to open new issues about various aspects of selective functors!

snowleopard commented

@glaebhoerl @copumpkin Brent Yorgey has pointed me to an IRC conversation about the Branchy type class, which I recorded here:

https://github.com/snowleopard/selective/blob/master/paper/irc-log-branchy.md

At the moment this is the earliest known (to me) occurrence of this idea :)

  • 👍2