MonadPlus instance for Logic has a bug

[dagit]

I noticed that runIdentity (observeAllT (mzero `mplus` pure 1)) was producing []. I then noticed this happened anytime mzero was the left argument to mplus.

The MonadPlus instance currently looks like this:

instance Monad m => MonadPlus (ML m) where
  mzero = ML empty
  mplus (toView -> m) n = fromView $ m >>= return . \case
       Nothing    -> Nothing
       Just (h,t) -> Just (h, cat t n) 
    where cat (ML l) (ML r) = ML $ l .>< r 

However, that first case means that mzero stops the rest of the computation. I changed the code to this:

instance Monad m => MonadPlus (ML m) where
  mzero = ML empty
  mplus (toView -> m) n = fromView $ m >>= \case
      Nothing -> toView n
      Just (h,t) -> return (Just (h, cat t n))
    where cat (ML l) (ML r) = ML $ l .>< r

And that seems to fix the issue. In particular, I have some local test code that compares breadth-first search and iterative deepening depth-first search and they now return equivalent results. And I was also able to confirm it now returns the same results as LogicT from Control.Monad.Logic. So I think the change I made is correct.

[dagit]

BTW, I uploaded a these ideas to hackage as logict-sequence so that I could use them more easily. I tried to give you and Oleg credit wherever I could. So I hope you don't mind: https://hackage.haskell.org/package/logict-sequence

[atzeus]

Whoops, that is indeed a bug. I'll fix it now.

[atzeus]

Fixed by 44e94ec