What do we gain and what do we break by distributing f over -> in Selective?

Selective2.hs

class Applicative f => Selective f where
  branch :: f (Either a b) -> f (a -> c) -> f (b -> c) -> f c
  branch ab f g = fmap (fmap Left) ab `select` fmap (fmap Right) f `select` g

  select :: f (Either a b) -> f (a -> b) -> f b
  select ab f = branch ab f (pure id)

  {-# MINIMAL branch | select #-} -- Defining in terms of both to double-check my work

filteredBy :: (Alternative f, Selective f) => f a -> (a -> Bool) -> f a -- from Staged Selective Parser Combinators
filteredBy f p = select (p' <$> f) empty
  where
  p' x
    | p x       = Right x
    | otherwise = Left ()

selectA :: Applicative f => f (Either a b) -> f (a -> b) -> f b -- Perhaps slow, but it gets the job done
selectA x y = (\e f -> either f id e) <$> x <*> y

-- per the selective package, we can also implement select with the desired behaviour for any Monad using >>=
selectM :: Monad f => f (Either a b) -> f (a -> b) -> f b
selectM x y = x >>= \e -> case e of Left  a -> ($a) <$> y -- execute y
                                    Right b -> pure b     -- skip y

class Applicative f => Selective2 f where
  -- f (a -> c) has become (f a -> f c)
  -- f (b -> c) has become (f b -> f c)
  branch2 :: f (Either a b) -> (f a -> f c) -> (f b -> f c) -> f c
  branch2 ab f g = fmap (fmap Left) ab `select2` fmap (fmap Right) f `select2` g

  -- f (a -> b) has become (f a -> f b)
  select2 :: f (Either a b) -> (f a -> f b) -> f b
  select2 ab f = branch2 ab f id

  {-# MINIMAL branch2 | select2 #-}

-- we can still implement this
filteredBy2 :: (Alternative f, Selective2 f) => f a -> (a -> Bool) -> f a
filteredBy2 f p = select2 (p' <$> f) (const empty)
  where
  p' x
    | p x       = Right x
    | otherwise = Left ()

-- …but not selectA2!
-- we need to switch on the Either, so we have to use fmap/<*>
-- our higher-order function takes its argument in f, so we can lift it in the Left case with pure
-- but then what?
-- 1. y returns in f, resulting in f (f b), and Applicative doesn’t give us any way to eliminate this nested f; Monad, ahoy
-- 2. we gain nothing from always using pure inputs that we couldn’t have done without Selective2
selectA2 :: Applicative f => f (Either a b) -> (f a -> f b) -> f b
selectA2 x y = ⁉️

-- by contrast, we _can_ implement our desired identifier-parsing, error-with-dependency behaviour:

-- A generalization of the unexpected method in Parsing from String -> p a to p String -> p a, so we don’t have to bind.
-- note that we can’t obtain the desired behaviour (failing with a given error message) with the signature p (String -> a);
-- in fact, that signature can _only_ fail without using the argument
class Alternative p => ParseFail p where
  unexpected :: p String -> p a

-- | Like filteredBy2, but it errors with the shown result
filteredBy2Fail :: (ParseFail f, Selective2 f, Show a) => f a -> (a -> Bool) -> f a
filteredBy2Fail f p = select2 (p' <$> f) (unexpected . fmap show)
  where
  p' x
    | p x       = Right x
    | otherwise = Left x


-- hooray, we can implement this with a Monad!
-- but note we’re not doing anything clever like e.g. selecting _some_ effects to replay; we can’t, generically
-- thus far, it’s not clear that this is much of a win
selectM2 :: Monad f => f (Either a b) -> (f a -> f b) -> f b
selectM2 x y = x >>= \e -> case e of Left  a -> y (pure a) -- execute y
                                     Right b -> pure b     -- skip y

-- we can analyze Selective programs statically because there aren’t any
-- continuations doing god-knows-what to worry about

-- what about Selective2?

-- anecdotally, I used this signature in a one-off to add “parse any identifier,
-- and then let me parse _the same identifier_ an arbitrary number of times further”
-- to a deterministic parser. it worked, tho it was a bit strange; in particular,
-- it didn’t sacrifice the ability to calculate the nullability or the first set for
-- the parsers.

-- but characterizing which effects get performed is where this gets weird.
-- replaying the effects (but not the choices) made sense in a parser, but does it
-- make sense _anywhere_ else?

-- finally, we’ve seen that we have something like Applicative < Selective2 < Monad,
-- but we further have Selective < Selective2, because you can relate select and
-- select2 via <*>. that is, given y :: f (a -> b), we obtain y' (f a -> f b) by
-- y' = (y <*>).

-- what does that mean?

-- who knows!

if I’m following correctly, it holds onto the function to show the invalid value with, and then when interpretation proceeds as far as the error, it’s the application of that to the result which collapses it from ErrorHandler into Error.

Yes, exactly!

The name "error handler" is not ideal though: ErrorHandler seems to have nothing to do with effect handlers, so it might just confuse readers.

One problem with this approach I forgot to mention is that it's pretty brittle: if you swap the branches in the example, it stops working, because the implementation of branch based on select needs to do an fmap on the left branch, which hits the "misplaced error handler" case. This seems to suggest that we want the branch-based version of selective functors. Or we need to figure out less brittle Functor/Applicative instances.