What is the fastest error monad in haskell?

Question

The Maybe/Either monad slows things down significantly. Does the use of some continuation monad for handling errors speeds things up? Is there such a thing as a "builtin continuation monad" or a "buitin error monad"? By builtin I mean something like ST.

Benchmark:

import Criterion.Main                                          

unsafeDiv x 0 = error "division by zero"                       
unsafeDiv x y = x `div` y                                      

safeDiv x 0 = Nothing                                          
safeDiv x y = Just (x `div` y)                                 

test1 :: Int -> [Int]                                          
test1 n = map (n `unsafeDiv`) [n,n-1..1]                       

test2 :: Int -> Maybe [Int]                                    
test2 n = mapM (n `safeDiv`) [n-1,n-2..0]                      

test3 :: Int -> Maybe [Int]                                    
test3 n = test3' Just [n-1,n-2..0]                             
  where test3' k []     = k []                                 
        test3' k (0:ns) = Nothing                              
        test3' k (n:ns) = test3' (k . (n:)) ns                 

main = defaultMain                                             
  [ bench "test1" (nf test1 100000)                            
  , bench "test2" (nf test2 100000)                            
  , bench "test3" (nf test3 100000)                            
  ] 

Answer 1

Normally using Maybe/Either should not slow things down. However, if Maybe/Either really is your bottleneck, you can try using a CPS-based Maybe monad like in the contstuff package. Another possibility is to use the Cont monad with escape routes.

In any case, I don't believe that Maybe and Either are the bottlenecks. You might be using them wrong for example by forcing too much. It is a common misbelief that all performance problems can be solved by using seq.

Answer 2

I've had some success with a rather horrible hand written monad that uses something like

newtype M r a = M { runM :: r -> (# Bool, a #) }

where I treat the Bool like the Maybe constructor and in the Nothing case put an error in for 'a'. I usually use this when I have more structure (an environment e, state, logs, etc.), so I'm not sure how well it would pay off when it is this simple but the monad looks something like:

instance Monad (M r) where
  return a = M (\_ -> (# True, a #))
  M f >>= k = M (\r -> case f r of
    (# True, a #) -> runM (k a) r
    (# False, _ #) -> (# False, undefined #))
  fail _ = M (\_ -> (# False, undefined #))

This has the benefit that we don't construct any thing on the heap, just the stack.

However, you need to be careful to be strict in all the right places. It is easy to accidentally build a thunk in your state which can kill your performance.

If you are feeling daring you can smuggle an unsafeCoerced error through in the 'a' slot on failure as well and extract it at the end, or you can just translate the Bool into a Maybe e but you need to be careful, because you don't want to build up a tower of unsafeCoerces defeating all the work you went through to get this far.

The effectiveness of this approach depends on how much the overhead of building and tearing down Maybe frames is vs. the mental and execution time costs of distributing the code for dealing about failure across a lot of different places in the code. Note how >>= has to effectively unwind the Failure case manually.

Answer 3

Control.Exception provides try/catch/finally in the IO monad. Which makes them usable in the ST monad as well (assuming you are careful.) The throw equations are usable in pure code. I suspect (though I have not verified) the exception mechanism is efficient. While not the same as using a monad transformer to provide failure control flow, sometimes exceptions are the right solution.