robrix · October 3, 2020 19:30 · Oct 3, 2020
diff --git a/Selective2.hs b/Selective2.hs
@@ -0,0 +1,100 @@
+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!