Haskell limit number of recursions

Question

I want to create a monad which will prevent more than 10 instances of recursion (which I am implementing by preventing more than 10 instances of >>=). My >>= definition seems kind of long and messy though, so I am wondering if there is a better way to do it.

I am including a factorial function which uses this monad as an example of how it could be used.

import Control.Monad.State
type LimitState a = (State Int (Either String a))
newtype Limiter a = Limiter {getState :: (LimitState a)}
instance Monad Limiter where
 return x = Limiter $ return $ Right x
 (Limiter state) >>= f = Limiter $ 
 do
 increment
 newCount <- get
 if newCount >= 10 
 then return $ Left "too many recursions"
 else getNextValue
 where 
 increment = do
 count <- get
 put (count + 1)
 getNextValue = do
 value <- state
 getState $ case value of
 (Left message) -> Limiter $ return $ Left message
 (Right v) -> f v
limitedFactorial :: Int -> Limiter Int
limitedFactorial 1 = return 1
limitedFactorial n = do
 recursive <- limitedFactorial (n - 1)
 return $ n * recursive
testLimitedFactorial =
 let (aValue, _) = runState (getState $ limitedFactorial 5) 0
 (uValue, _) = runState (getState $ limitedFactorial 11) 0
 in print aValue >> print uValue 

Answer 1

Sheriff voice: Halt! You are breaking the laws!

Your monad breaks the right- and left-identity law of >>=:

k >>= return = k -- right identity
return a >>= f = f a -- left identity

Suddenly, it makes a big difference whether I call return at the end of my function:

do
 replicateM 9 actions -- fine
do
 k <- replicateM 9 actions
 return k -- fails

That simply breaks to much. Your Monad is also missing its Functor and Applicative instances, which would make it easy to "cheat". And if you implemented a fmap that limits the number of fmaps, you start to break Functor laws. Note that due to the Monad/Functor laws, we should be able to rewrite

limitedFactorial :: Int -> Limiter Int
limitedFactorial 1 = return 1
limitedFactorial n = do
 recursive <- limitedFactorial (n - 1)
 return $ n * recursive

to

limitedFactorial :: Int -> Limiter Int
limitedFactorial 1 = return 1
limitedFactorial n = fmap (n *) $ limitedFactorial (n - 1)

If you were to limit that, you would break fmap id = id immediately.

But even without all of these quirks, at long last, there's nothing preventing the user to use recursion:

example :: Limit Int
example = return 1 -- fine
evil :: Int -> a -> Int
evil x _ = if x > 0 then 1 + evil (x - 1) undefined else 0
do
 liftM (evil 100000000) example -- recursion!

So conceptionally, your Monad is broken, unfortunately.

Further review

1. Your code uses names from your imports. state is a function defined in Control.Monad.State, so it makes your instance slightly hard to read.
2. You use increment only once, so it makes sense to inline it.