A very common pattern in functional programming is tail recursion . In a tail-recursive function, an extra argument (called the accumulator ) is added to the function, where the result is accumulated. These two implementations of list reverse illustrate the point:

-- Not tail recursive
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (x:xs) = xs ++ [x]

-- Tail recursive
myReverse' :: [a] -> [a]
myReverse' xs = myReverseAux xs [] where
  myReverseAux [] ys = ys
  myReverseAux (x:xs) ys = myReverseAux xs (x:ys)

The tail recursive style is more difficult to reason about. Usually, their main advantage is that they use less stack memory. In this case though, runtime improves too: myReverse xs is quadratic time, myReverse' xs is linear time. (Think about why that is).

Whenever we introduce auxiliary variables in this manner, we are in effect introducing background state into the computation. This means we could be using the state monad instead. Try it out by completing the following definition:

import Control.Monad.State

myReverse'' :: [a] -> [a]
myReverse'' xs = evalState (myReverseAux xs) [] where
  myReverseAux :: [a] -> State [a] [a]
  myReverseAux []     = undefined -- TODO
  myReverseAux (x:xs) =
    do
      modify undefined -- TODO
      myReverseAux xs

An alternative but equivalent presentation of monads that you sometimes encounter is this:

class AltMonad m where
  returnA :: a -> m a
  joinA   :: m (m a) -> m a
  fmapA   :: (a -> b) -> m a -> m b

That is, instead of using return and >>= as our basic operations, we choose return , join and fmap .

1. Define an AltMonad instance on Maybe

   instance AltMonad Maybe where
     -- returnA :: a -> Maybe a
     returnA = undefined --TODO
     -- joinA :: Maybe(Maybe a) -> Maybe a
     joinA   = undefined --TODO
     -- fmapA :: (a -> b) -> Maybe a -> Maybe b
     fmapA   = undefined --TODO

2. Define an AltMonad instance on lists.

   instance AltMonad [] where
     -- returnA :: a -> [a]
     returnA = undefined --TODO
     -- joinA :: [[a]] -> [a]
     joinA   = undefined --TODO
     -- fmapA :: (a -> b) -> [a] -> [b]
     fmapA   = undefined --TODO
   

3. Show how the standard definition of monads follows from the alternative presentation by completing the following instance declaration.

   {-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
   -- put the above line at the top of your file
   instance Monad m => AltMonad m where
     returnA = return
     joinA   = undefined -- TODO
     fmapA   = undefined -- TODO
   

4. Show how the standard definition of monads can be obtained from the alternative presentation by completing the below instance declarations.

   {-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
   -- put the above line at the top of your file
   instance AltMonad m => Functor m where
     fmap = fmapA
   
   instance AltMonad m => Applicative m where
     pure = returnA
     fm <*> xm = joinA $ fmapA (\x -> fmapA ($x) fm) xm
   
   instance AltMonad m ==> Monad m  where
     returnA = return
     (>>=)   = undefined -- TODO
   

5. AltMonad also comes with laws. Here they are:

   fmapA id m             == m
   fmapA (f . g) m        == fmapA f (fmapA g m)
   fmapA f (returnA x)    == returnA(f x)
   fmapA f (joinA mm)     == joinA (fmapA (fmapA f) m)
   joinA(returnA m)       == m
   joinA(fmapA returnA m) == m
   joinA(fmapA joinA mmm) == joinA(joinA mmm)
   

   (At this point, the discerning reader may be able to guess why this presentation is less popular in computer science.) Given your definitions above, can you derive one set of laws from the other, and vice versa?

You may want to comment out the monad instances above once you're done playing with them. They're likely to confuse Haskell by introducing circularities into the type class resolution.