为什么catamorphism产生的未使用值被评估？

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

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