Monad transformer representing an infinite chain of actions?

Viewed 111

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?

1 Answers

The counterexample at this link works for your WhileT Maybe, too.

-- to make these things a bit more convenient to type/read
fromListW :: [a] -> WhileT Maybe a
fromListW [] = WhileT Nothing
fromListW (x:xs) = WhileT (Just (x, fromListW xs))

xs = fromListW [1,2]

f 1 = fromListW [11]
f 2 = fromListW [21, 22]

g 11 = fromListW [111]
g 21 = fromListW []
g 22 = fromListW [221, 222]

Then, in ghci:

> (xs >>= f) >>= g
WhileT {uncons = Just (111,WhileT {uncons = Just (222,WhileT {uncons = Nothing})})}
> xs >>= (\x -> f x >>= g)
WhileT {uncons = Just (111,WhileT {uncons = Nothing})}
Related