为什么对变质产生的未使用价值进行评估？

Question

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

{-# 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

我认为这与绑定运算符有关，但以下代码需要 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.

后挂起

为什么对变质产生的未使用价值进行评估？

Why is unused value produced by catamorphism evaluated?

haskell

lazy-evaluation

recursion-schemes