Concoct a correct "Free Alternative" about free HOT 8 CLOSED

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?

from free.

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.

from free.

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.

from free.

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.

from free.

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

from free.

Merged 12a9c00. Thanks @vklj!

from free.

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

from free.

Shipped in free 4.6.

from free.