Concoct a correct "Free Alternative"

[ekmett]

My working assumption is it'd look something like:

data AltF f a where
  Pure :: a -> AltF f a
  Ap   :: f a -> Alt f (a -> b) -> AltF f b
#if __GLASGOW_HASKELL__ >= 707
  deriving Typeable
#endif

data Alt f a = Alt [AltF f a]
#if __GLASGOW_HASKELL__ >= 707
  deriving Typeable
#endif

-- | Given a natural transformation from @f@ to @g@, this gives a canonical monoidal natural transformation from @'Alt' f@ to @g@.
runAlt :: forall f g a. Alternative g => (forall x. f x -> g x) -> Alt f a -> g a
runAlt u xs0 = go xs0 where
  go :: Alt f a -> g a
  go (Alt xs) = foldr (\a r -> go2 a <|> r) empty xs

  go2 :: AltF f a -> g a
  go2 (Pure a) = pure a
  go2 (Ap f x) = flip id <$> u f <*> runAlt u x

instance Functor (AltF f) where
  fmap f (Pure a)   = Pure (f a)
  fmap f (Ap x y)   = Ap x (fmap f <$> y)

instance Functor (Alt f) where
  fmap f (Alt as)   = Alt (fmap f <$> as)

Thoughts?

[vlopezj]

empty <|> a  == a <|> empty == a
(a <|> b) <|> c == a <|> (b <|> c)
empty <*> a == empty

Are there any other laws that every Alternative instance should follow?

[ekmett]

Basically we need to choose between the equivalent of the left distribution and left catch laws from the old MonadPlus reform proposal

I'd say the distribution law is the one that matters, hence the use of [] above.

[ekmett]

So we'd want

(a <|> b) <*> c = (a <*> c) <|> (b <*> c)

I think you can get the catch law from the abuse of lists there if you target an Alternative for runAlt that satisfies that law as well, but I haven't made that rigorous.

[vlopezj]

I just pushed a working prototype to a new branch. It's not very clean, with lots of currying, but I ran some tests and it seems to work fine.

Left catch might hold, but runAlt would not be an homomorphism anymore. There's an example using a ZipList alternative functor in the test file.

[ekmett]

Hrmm, I wonder if we can accomplish this and still retain Twan's f a -> Alt f (a -> b) -> Alt f b backend somehow.

[ekmett]

Merged 12a9c00. Thanks @vklj!

[vlopezj]

My pleasure :) . I'll close the issue then.

[ekmett]

Shipped in free 4.6.