There is a nice Free Alternative in the great free package, which lifts a Functor to a left-distributive Alternative.
That is, the claim is that:
runAlt :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g a
is an Alternative homomorphism, with liftAlt. And, indeed, it is one, but only for left-distributive Alternative instances.
Of course, in reality, very few Alternative instances are actually left-distributive. Most of the alternative instances that actually matter (parsers, MaybeT f for most Monad f, etc.) are not left-distributive. This fact can be shown by an example where runAlt and liftAlt do not form an Alternative homomorphism:
(writeIORef x False <|> writeIORef True) *> (guard =<< readIORef x)
-- is an IO action that throws an exception
runAlt id $ (liftAlt (writeIORef x False) <|> liftAlt (writeIORef True))
*> liftAlt (guard =<< readIORef x)
-- is an IO action that throws no exception and returns successfully ()
So runAlt is only an Alternative homomorphism for some Alternatives, but not all. This is because the structure of Alt normalizes all actions to distribute over the left.
Alt is great because, structurally, Alt f is a lawful Applicative and Alternative. There isn't any possible way to construct a value of type Alt f a using the Applicative and Alternative functions that don't follow the laws...the structure of the type itself is what makes it a free Alternative.
Just like, for lists, you can't construct a list using <> and mempty that doesn't respect x <> mempty = x, mempty <> x = x, and associativity.
I've written a Free alternative that doesn't enforce the Applicative and Alternative laws, structurally, but does yield a valid Alternative and Applicative homomorphism with runAlt/liftAlt:
data Alt :: (* -> *) -> * -> * where
Pure :: a -> Alt f a
Lift :: f a -> Alt f a
Empty :: Alt f a
Ap :: Alt f (a -> b) -> Alt f a -> Alt f b
Plus :: Alt f as -> Alt f as -> Alt f as
instance Functor f => Functor (Alt f) where
fmap f = \case
Pure x -> Pure (f x)
Lift x -> Lift (f <$> x)
Empty -> Empty
Ap fs xs -> Ap ((f .) <$> fs) xs
Plus xs ys -> Plus (f <$> xs) (f <$> ys)
instance Functor f => Applicative (Alt f) where
pure = Pure
(<*>) = Ap
instance Functor f => Alternative (Alt f) where
empty = Empty
(<|>) = Plus
structurally, Alt f is not an actual Applicative, because:
pure f <*> pure x = Ap (Pure f) (Pure x)
pure (f x) = Pure (f x)
So pure f <*> pure x is not the same as pure (f x), structurally. Not a valid Applicative, right off the bat.
But, with the given runAlt and liftAlt:
liftAlt :: f a -> Alt f a
liftAlt = Lift
runAlt :: Alternative g => (forall x. f x -> g x) -> Alt f a -> g a
runAlt f = \case
Pure x -> pure x
Lift x -> f x
Empty -> empty
Ap fs xs -> runAlt f fs <*> runAlt f xs
Plus xs ys -> runAlt f xs <|> runAlt f ys
And runAlt here does indeed act as a valid Applicative homomorphism with a given natural transformation...
One could say that my new Alt f is a valid Alternative and Applicative when quotiented by the equivalence relationship defined by runAlt, i suppose.
Anyway, this is only slightly unsatisfying. Is there any way to write a free Alternative that is structurally a valid Alternative and Applicative, without enforcing left distributivity?
(In particular, I'm actually interested in one that follows the left catch law, and enforces it structurally. This would be a separate and also interesting thing, but not completely necessary.)
And, if there isn't any way, why not?