3

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

1 回答 1

7

请注意，>>=对于 的第一个参数是严格的，Maybe因此即使k >>= \x -> Nothing总是会被评估为弱头正常形式（这意味着在这种情况下它具有形式or ，其中可以是未评估的重击）。NothingkJust _Nothing_

在你的情况下，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挂起。

于 2016-10-16T21:56:09.663 回答