为什么计算 catamorphism 生成的未使用值？

Question

为什么计算 catamorphism 生成的未使用值？

3

我原以为以下代码会运行并立即退出，因为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

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

- bwroga

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alec · Accepted Answer

请注意，对于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”之后卡住了。