Change semantics for IterT's Alternative and MonadPlus instances

[vlopezj]

These are the current instances for IterT of Alternative and MonadPlus. Both of them were added when the Iter module was first commited; they are equivalent to the ones that would be created by GeneralizedNewtypeDeriving.

instance MonadPlus m => Alternative (IterT m) where
  empty = IterT mzero
  {-# INLINE empty #-}
  IterT a <|> IterT b = IterT (mplus a b)
  {-# INLINE (<|>) #-}

instance MonadPlus m => MonadPlus (IterT m) where
  mzero = IterT mzero
  {-# INLINE mzero #-}
  IterT a `mplus` IterT b = IterT (mplus a b)
  {-# INLINE mplus #-}

In Capretta's slides, a race function is defined. It tries several approaches for the same result (some of them, maybe non terminating), and the earliest one to succeed is picked out. Venanzio b is equivalent to Iter b.

race :: Venanzio b -> Venanzio b -> Venanzio b 
race (Now b0) _ = Now b0
race (Later _) (Now b1) = Now b1
race (Later c0) (Later c1) = Later (race c0 c1)

If race is generalized to the IterT m b, the following instances can be defined. They are analogous to the ones for the MaybeT transformer, and satisfy the same subset of laws : namely, monad plus with left catch.

instance (Monad m) => Alternative (IterT m) where
  empty = never
  {-# INLINE empty #-}
  (<|>) = mplus 
  {-# INLINE (<|>) #-}

instance (Monad m) => MonadPlus (IterT m) where
  mzero = never
  x `mplus` y = IterT $ do
    x' <- runIterT x
    case x' of
      l@(Left _) -> return l
      Right a -> do
        y' <- runIterT y
        case y' of
          l@(Left _) -> return l
          Right b    -> return . Right $ a <|> b

These new semantics might be more useful, but they would break the API.

[ekmett]

We can do that with a major version bump and a clearly worded CHANGELOG entry. I don't think anybody but me has adopted IterT yet.

[vlopezj]

On the other hand, this new instances are not fully satisfactory. Ideally, if the underlying monad implements MonadPlus, the first computation which completes and does so without errors should be returned.

The instance for plain IterT Identity (which is not MonadPlus) is quite straightforward, and causes no conflicts. I'll add that one first, and then think whether it's possible to make IterT into a true MonadPlus transformer.

[ekmett]

The problem with making instances for IterT Identity is that it precludes any general solution by overlap and requires a FlexibleInstance, which in my experience makes its selection brittle.

Of course we can make a separate Control.Monad.Iter that has a concrete Iter with that instance, which would let us have a nice, explainable

data Iter a = Stop a | Step (Iter a)

with obvious racing.

[vlopezj]

The behaviour described above is now in commit 7b3cbcb , on the iter-monadplus branch.

The approach is similar to the one for the ErrorT monad transformer, where the behaviour of the underlying monad is disregarded when implementing MonadPlus.

[ekmett]

I'm cautiously optimistic about the new change. The main question I'd have is how to get the word out about it.

[vlopezj]

How about some explanation at the top of the Haddock page, and an usage example? Together with the major version bump, it could be enough for interested users to notice.

[ekmett]

That sounds like a plan to me. Feel free to merge into master.

On Wed, Jul 9, 2014 at 11:21 AM, Víctor López Juan <notifications@github.com

wrote:

How about some explanation at the top of the Haddock page, and an usage
example? Together with the major version bump, it could be enough for
interested users to notice.

—
Reply to this email directly or view it on GitHub
#52 (comment).

[vlopezj]

• Documentation
• Change log and version bump
• New instance

[ekmett]

Have I mentioned that you, sir, are awesome?