为什么Haskell不能优化这个？(在Maybe monad中没有任何东西被不必要地传播.)

Question

让我们开始吧

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

这是一个简单的函数,它只是将>>=一个Maybe值反复推入一个简单的\y -> Just y函数中.

现在,该计划

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

一瞬间跑得很快.但是,该计划

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

即使我编译ghc -O(GHC 7.8.3),也需要几秒钟才能完成.

这意味着Haskell无法优化此功能.Nothing即使没有必要,它也会被反复推入一个函数中.

我的问题是,为什么？为什么不能推断Nothing总是最终如同Nothing反复推.. 换句话说,为什么它不能立即在第一次短路Nothing？

Answer 1

你的函数是一个很好的例子,它很慢,因为它是尾递归的.在严格的语言中,尾递归函数通常是首选,因为它们通常会带来更好的性能(在时间和空间上).在懒惰的尾部递归并不是那么有益.实际上,函数的非尾递归变体是:

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

上述仍将环路n时候x是Just something.但是,它会在常量空间中执行此操作,而不像在第二个参数中构建大型thunk的原始代码.更妙的是,当x是Nothing时,上面的代码将立即返回.

我确实意识到这并没有真正回答你关于"为什么"GHC无法对此进行优化的问题.但希望,它可以表明这些优化非常微妙,并且通常涉及归纳推理.期望编译器优化它可能要求有点过多.