haskell - 为什么对变质产生的未使用值(value)进行评估？

Question

我预计以下代码会立即运行并退出，因为 p 从未实际使用过，而是运行了超过 7 分钟，然后似乎被操作系统杀死。

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad (liftM2)

main = print $ ((product' 1 >>= \p -> Nothing) :: Maybe Integer)

data Term f = In { out :: f (Term f) }

type Algebra f a = (f a -> a)

cata :: (Functor f) => Algebra f a -> Term f -> a
cata g t = g $ fmap (cata g) $ out t

type CoAlgebra f a = (a -> f a)

ana :: (Functor f) => CoAlgebra f a -> a -> Term f
ana g a = In $ fmap (ana g) $ g a

data A a = A (Maybe Integer) [a] | B deriving (Functor)

product' :: Integer -> Maybe Integer
product' i = cata h $ ana g $ fmap Just [i..1000]
  where g (x:xs) = A x $ replicate 10 xs
        g [] = B
        h (A k l) = foldr (liftM2 (*)) k l
        h B = Just 1

我以为这与绑定(bind)运算符有关，但下面的代码需要 9 秒才能运行:

import Control.Monad (liftM2)
import Data.Foldable (foldr1)

main = print $ ((p >>= \p' -> Just p') :: Maybe Integer)

p :: Maybe Integer
p = foldr1 (liftM2 (*)) $ fmap Just [1..100000]

这段代码立即退出:

import Control.Monad (liftM2)
import Data.Foldable (foldr1)

main = print $ ((p >>= \p' -> Nothing) :: Maybe Integer)

p :: Maybe Integer
p = foldr1 (liftM2 (*)) $ fmap Just [1..100000]

Answer 1

请注意 >>= 在 Maybe 的第一个参数中是严格的，所以即使 k >>=\x -> Nothing始终是 Nothing，k 仍然被评估为弱头部范式(这意味着在这种情况下它具有 Just _ 或Nothing，其中 _ 可以是未计算的 thunk)。

在您的例子中，k 是product' 1。您会注意到，只是尝试将其评估为较弱的正常头部形态会挂起。事实上，您可以看到 product' x 可能会花费很长时间，因为随着 1000 - x 越来越大，它会变得越来越慢。在我的笔记本电脑上，即使 product' 995 也需要很长时间(-O2 也是如此)。

---

您的基准实际上并没有显示您认为的那样。 >>= 在第一个参数中确实是严格的，但仅限于 WNHF(不是一直向下)。为了证明我的观点，请注意以下立即退出。

import Control.Monad (liftM2)
import Data.Foldable (foldr1)

main = print $ ((p >>= \_ -> Just 1) :: Maybe Integer)

p :: Maybe Integer
p = foldr1 (liftM2 (*)) $ fmap Just [1..100000]

您的第二个代码片段挂起的原因是它在尝试进行乘法(相当大)以打印结果时卡住了。如果您忽略结果(就像我在上面所做的那样)，那不会发生 - 结果保持未评估状态。另一个线索:您的第二个代码片段在开始打印 Just 之后挂起。