Add Alternative and MonadPlus instances

[dminuoso]

Rename 'empty' to 'failed'

Addresses #11

[dminuoso]

Note, the reason I renamed empty to failed is to have a combinator whose name tells the user what it does. empty from Alternative is still re-exported for compatibility. (<|>) is kept as is for two reasons:

a) It guarantees better associativity instead of relying on RULES to fire, so slightly better guarantees for a parser to be constructed the right way. b) It avoids breaking code that, one way or another, relies on infixr 6.

[AndrasKovacs]

I haven't used phase control inline before, quick question: I see inline [1] for <|>, is that the earliest possible, or would inline[2] also work? Intuitively, I'd like to inline <|> as early as possible because un-inlined <|> blocks lots of simplification. Would it work to not have phase control at all, or would the rewrite never fire in that case?

[dminuoso]

In regular configuration GHC has phases 2, 1 and then 0. So this becomes a toss-up, we can remove the phase control, but then (<|>) might get inlined first, preventing the reassociation rule from firing.

The benefits depend on whether you more likely use Control.Applicative.(<|>) or not, and whether GHC can do enough case-of-case to produce the same code without the reassociation rule.

Note: Each phase still have 4 iterations, so even at phase 1 we have at least 8 simplifier iterations going on.

[AndrasKovacs]

I don't see change in benchmark code output, so I guess this is OK.

Could you rename failed to fail though? That's what the implementation is and there's no past tense in any other function name right now.

[raehik]

Doesn't fail overlap with fail :: MonadFail m => String -> m a? Which is included in the prelude on 9.4 (I think it has been for a while).

[AndrasKovacs]

Uhh, right... We don't want to shadow Prelude. I don't have a better idea, let's go with failed.