Decouple Monad from Applicative

[raimohanska]

I'm afraid it's not always correct to assume that a Monad is also an Applicative. At least I tried to implement the specs into Bacon.js today, for an excersise, and run into issues because of this assumption. I'm not sure how familiar you're with Bacon.js, but I'll try to explain the case anyway.

Now an EventStream in Bacon.js is clearly a Monadic structure: the flatMap method (aliased now as chain) of EventStream has one parameter which is a function that creates a new EventStream for each value in the original stream. In combination with EventStream.of we have a nice Monad. Except.

The Applicative interface for EventStreams doesn't make much sense, at least if based on flatMap: the result stream a.ap(b) would take apply each function from the source stream to all (or one?) subsequent elements in the stream b. It would make more sense to base ap on combine or even zip, but I'd rather not have EventStream implement Applicative because of this ambiguity.

In Haskell, you can declare Monad without Applicative. Why not in Fantasy Land?

The fantasy-land version of Bacon.js is in the fantasy-land branch. I'm planning to bring that to master, if I can come up with a nice solution. The current EventStream/Applicative one seems to be compliant, but I would never use it because Applicative through flatMap just makes no sense.

I'd like to have EventStream implement Functor and Monad (no Applicative), and Property implement Functor and Applicative (and a Duck Monad (Property.flatMap returns an instance of EventStream)).

Please ask for more details if this made no sense to you :)

[raimohanska]

I added Monoid for EventStream. It already had concat so I only had to add a synonym EventStream.empty for Bacon.never. What a fun excercise!

[Twisol]

In Haskell, you can declare Monad without Applicative. Why not in Fantasy Land?

This is a known issue, and Haskellers are generally unsatisfied with the current state of affairs. The Haskell situation is an artifact of monads being used in Haskell early on (to control side-effects and I/O), before applicatives were also found to be generally useful. The Monad and Applicative class instances are expected to agree even though the standard library doesn't require it. Mathematically, all monads are applicative functors by definition.

I don't know Bacon.js well enough to suggest any specific alternatives. Does your flatMap meet the Monad axioms in all cases (barring unavoidable semantics of mutation)? What if you implemented flatMap in terms of combine/zip - what effects would that have on the monadic semantics?

[markandrus]

chain and map give you ap. In the Fantasy Land spec:

• Applicative's ap; derivable as function(m) { return this.chain(function(f) { return m.map(f); }); }

Did you try this default definition? There may be multiple and sometimes more useful ways to write ap. EventStream might be one such case, but I don't know Bacon.js.

[raimohanska]

Guys, thanks for your replies!

@markandrus My implementation of EventStream.ap is identical to the default one. If I have to choose one, I might go for the zip based approach, though. That might be useful for someone :) @Twisol I'm tempted to say it meets the Monad axioms. Are we talking about the laws in here? @Twisol you cannot implement flatMap in terms of combine/zip, can you?

[raimohanska]

The issue is not whether I can implement Applicative, but more that I'd rather not because of the many different possible ways.

Like, if [] is Applicative, should it use >>= or zip? Depends on situation, probably.

[Twisol]

@raimohanska RIght, those laws. It's best if you semi-rigorously prove that those axioms hold for your implementation, since it's easy to miss important edge cases.

When I said "implement it in terms of combine/zip", I meant that there may be a Monad implementation associated with the combine/zip-based Applicative you prefer, so you may want to start there and find a new flatMap for which the automatically-provided ap is equivalent to the new one. See if the semantics for the new flatMap make sense.

It may turn out that either of your ap and flatMap definitions don't preserve the appropriate axioms, or that you really do have two interesting sets of instances. Integers have at least two Monoid instances - Sum and Product - so this isn't obviously impossible. I would be a little surprised though.

[puffnfresh]

Yes, Haskell stuffed up by not realising the hierarchy of Apply => Applicative => Monad. Fantasy Land doesn't have that problem.

Anyway, even in Haskell, for every Monad you can get an Applicative - the opposite is of course not true.

instance Monad m => Applicative (WrappedMonad m) where
    pure = WrapMonad . return
    WrapMonad f <*> WrapMonad v = WrapMonad (f `ap` v)

Where Haskell's ap is actually defined over Monad:

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap = liftM2 id

liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2 = do
  x1 <- m1
  x2 <- m2
  return (f x1 x2)

So if we can implement chain and of for EventStream but the above doesn't work, then the Monad laws must be broken somewhere :frowning:

And yes, things can have multiple Applicatives. That's what I was trying to get at with this part of the spec:

If there's more than a single way to implement the methods and laws, the implementation should choose one and provide wrappers for other uses.

Haskell does the same thing:

newtype ZipList a = ZipList { getZipList :: [a] }

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

I'd say the Applicative for a data type should do the same as the Monad (if one is defined). That'd be the least surprising. Provide a wrapper for the other behaviour(s).

[philipnilsson]

An interesting feature of Applicatives is that they can not be used to change the 'control flow'. E.g. for IO

(\fire -> if fire then a else b) <$> fireZeMissiles <*> petTheKoala

will result in the side effects of fireZeMissiles always executing, even if fire is false. The applicative interface could perhaps (for IO) define a combinator that runs its arguments in parallell, as the order things complete does not affect the result.

Perhaps one could standardize on a "parallel applicative" type class, which the zip-applicative for lists and event streams could fulfill, as they are in a sense also "parallel".

[SimonRichardson]

I'm closing this one, reopen if you wish to suggest other wise.