# Haskell limit number of recursions

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)}

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


# 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!


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.