ekmett / machines

Networks of composable stream transducers
Other
339 stars 46 forks source link

Applicative and Monad instances for Mealy are inconsistent #103

Closed greenrd closed 6 years ago

greenrd commented 6 years ago
> let m1 = unfoldMealy (\s a -> (a + s, a + s)) 0
> let mf = unfoldMealy (\s a -> (\b -> a + s + b), a + s)) 0
> cosieve (mf <*> m1) $ 1 :| [2,3]
12
> cosieve (mf `ap` m1) $ 1 :| [2.3]
9

<*> and ap are supposed to be the same.

greenrd commented 6 years ago

It looks difficult to solve this:

  1. Could we change the Monad instance to make it consistent with the Applicative instance? No, because there's no way to both combine and simultaneously update Mealy machines - it doesn't make sense in general.
  2. Could we change the Applicative instance to make it consistent with the Monad instance? No, because doing so would break the identity Applicative law. This suggests that the Monad instance is fundamentally broken.

One solution is to remove the Monad, MonadFix, MonadZip and MonadReader instances for Mealy.

MealyT has the same issue, and its Monad instance is not only inconsistent with its Applicative instance, but also inconsistent with Mealy's Monad instance!