Why isn't Haskell able to optimize this? (Nothing gets propagated needlessly in the Maybe monad.)

Question

Let's start with

boom :: Int -> Maybe a -> Maybe a
boom 0 x = x
boom n x = boom (n-1) (x >>= (\y -> Just y))

It's a simple function that just repeatedly shoves (>>=) a Maybe value into a trivial \y -> Just y function.

Now, the program

main = do
    let z = boom 10 (Nothing :: Maybe Int)
    putStrLn $ show z

runs very quickly, in a split second. However, the program

main = do
    let z = boom 10000000 (Nothing :: Maybe Int)
    putStrLn $ show z

takes a few seconds to finish, even if I compile with ghc -O (GHC 7.8.3).

This means that Haskell is not able to optimize this away. Nothing gets shoved repeatedly into a function even if there is no need for it to do so.

My question is, why? Why can't it deduce that a Nothing always ends up as Nothing in repeated shoving? In other words, why isn't it able to immediately short-circuit at the first Nothing?

Answer 1

Yours is a nice example of a function which is slow because it is tail recursive. In strict languages, tail recursive functions are usually preferred since they typically lead to a better performance (in both time and space). In lazy ones tail recursion is not so beneficial. Indeed, a non tail recursive variant of your function is:

boom :: Int -> Maybe a -> Maybe a
boom 0 x = x
boom n x = x >>= (\y -> boom (n-1) (Just y))

The above will still loop n times when x is a Just something. However, it will do that in constant space unlike the original code which builds a large thunk in its second argument. Even better, when x is Nothing, the the above code will return immediately.

I do realize that this does not really answer your question about "why" GHC is not able to optimize this. But hopefully, it can show that these kinds of optimizations are quite subtle, and often involve an inductive reasoning. Expecting the compiler to optimize this is probably asking a bit too much.