5
\$\begingroup\$

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   
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.