I attempted to implement a monad transformer representing an infinite chain of actions, like this:
import Control.Arrow
import Control.Monad
import Data.Functor.Classes
import Data.Functor.Identity
import Data.Monoid
import Data.Semigroup
import Text.Read
import qualified Control.Monad.Trans.Class as T
newtype WhileT m a = WhileT {uncons :: m (a, WhileT m a)}
instance T.MonadTrans WhileT where
lift m = WhileT $ do
x <- m
pure (x, T.lift m)
headW :: Functor m => WhileT m a -> m a
headW (WhileT m) = fmap fst m
tailW :: Functor m => WhileT m a -> m (WhileT m a)
tailW (WhileT m) = fmap snd m
drop1 :: Monad m => WhileT m a -> WhileT m a
drop1 m = WhileT (tailW m >>= uncons)
dropN :: Monad m => Int -> WhileT m a -> WhileT m a
dropN n = appEndo (stimes n (Endo drop1))
instance Functor m => Functor (WhileT m) where
fmap f (WhileT m) = WhileT (fmap (f *** fmap f) m)
instance Monad m => Applicative (WhileT m) where
pure x = WhileT (pure (x, pure x))
(<*>) = ap
instance Monad m => Monad (WhileT m) where
WhileT m >>= f = WhileT $ do
(x, xs) <- m
y <- headW (f x)
let ys = xs >>= drop1 . f
pure (y, ys)
The name WhileT is after C's while. It can be easily seen that WhileT Identity is a monad.
But what about other choices of m? In particular, judging by some experiments, WhileT Maybe seems to be equivalent to ZipList. But it is already known that there is no instance Monad ZipList. Does this mean WhileT isn't really a monad transformer?
Edit
It seems this is the correct of way of implementing instance Monad (WhileT m):
import Control.Applicative
instance MonadPlus m => Applicative (WhileT m) where
pure x = WhileT (pure (x, empty))
liftA2 = liftM2
(<*>) = ap
instance MonadPlus m => Alternative (WhileT m) where
empty = WhileT empty
WhileT xs <|> WhileT ys = WhileT (xs <|> ys)
instance MonadPlus m => Monad (WhileT m) where
WhileT xs >>= f = WhileT $ do
(y, ys) <- xs
uncons (f y) <|> uncons (ys >>= f)
instance MonadPlus m => MonadPlus (WhileT m)
Now WhileT Identity isn't even a monad, but hey, it was just (->) Natural.
Now WhileT Maybe is equivalent to []. What about now? Any choice of m where WhileT m violates the monad laws?