Having `ap` depend on `map` can introduce loops

[hdgarrood]

Before #229 was merged, ap depended on bind and pure. Now that #229 has been merged, ap depends on bind and map.

This means that defining apply = ap as well as map = liftA1 will cause loops. When you try to use map with such a type, the following happens:

• map
• is implemented via liftA1,
• which calls apply,
• which is implemented via ap,
• ... which calls map, and we loop.

Effect is one such type; this was causing failures in purescript/purescript-refs#29 (comment).

I think the law changes in #229 were correct, but perhaps changing ap to have a Bind constraint rather than a Monad constraint should be reverted? I think changing the rules for when it's safe to use these default implementation functions is probably too dangerous a breaking change to be justifiable. Maybe default implementation functions should only be allowed to use type class members from classes which are below the class which they are providing a default implementation for in the hierarchy? That is, it's fine for liftA1 to depend on both apply and pure, because they are members from Apply and Applicative respectively, which are both below Functor. Also, it's fine for ap to depend on both bind and pure, because they are from Bind and Applicative, which are both below Apply. However, it's not fine for ap to depend on map, because that's from Functor, which is above Apply.

[JordanMartinez]

The change should probably be reverted until we can prevent this situation from occurring via a compiler error or something (and I'm not sure how difficult it would be to do that). I think it's too easy to make this mistake, even if it will rarely happen. It's not obvious what causes this loop. While we could document it, I don't think that's the solution that should be used here.

[hdgarrood]

I agree that we shouldn’t leave ap as-is, but I would rather not just revert the whole change either. I think my preference right now would be to revert the code changes so that ap has a Monad constraint and depends on only bind and pure, but change the Bind class’s Apply Superclass law to this:

apply f x = f >>= \f’ -> map f’ x

so that we still ensure that Bind and Apply are compatible.