Почему оценивается неиспользованная ценность, произведенная катаморфизмом?

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, где _ может быть неоцененным

В твоем случае, 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,