递归构造一个无限的、惰性的 Monad 值

Question

作为练习，我尝试在 monad 内递归地构造一个无限的、惰性的列表。

基本上，相当于nat，但是是一元的，monat：

nat :: Int -> [Int]
nat n = n : nat (n+1)

monat :: Monad m => Int -> m [Int]
monat n = return n >>= \n -> (n:) <$> monat (n+1)

但monat并不是真正懒惰地求值：如果不计算所有元素，就不可能获得第一个元素：

ghci> take 5 $ nat 0
[0,1,2,3,4]

ghci> take 5 <$> (monat 0) :: Maybe [Int]
... never ending computation ...

我怀疑问题一定在于fmapor >>=，因为它们是我在那里使用但不在 中使用的唯一额外函数nat。然而，我查看了他们的实现，但不明白为什么或在哪里打破了懒惰：

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

• 您能帮我理解为什么列表中的列表monat不是延迟计算的吗？

• 除了分析代码之外，还有什么方法可以理解为什么计算没有结束？例如，我可以做一些事情，比如暂停 GHCi 中的评估并查看一些最新的堆栈跟踪帧，以了解它在哪里循环？如何？

Answer 1

无限循环的原因很简单，函子的fmap/需要知道输入是否是或。因为它仅在存在时应用该函数，否则它将传播.<$>MaybeNothingJustJustNothing

您的函数monat没有指定结果是否应该是Nothingor Just。理论上，两者都是您定义的方程的不动点monat。更实际的是，您可以将其视为推迟每次递归调用之间monat的选择。这样一来，它就永远不会真正做出选择。NothingJust

解决此问题同时仍保留一元接口的一种方法是使用ListTmonad 转换器（来自 的转换器，而不是< 0.6 和< 2.3list-t中损坏的转换器）。这个 monad 转换器就像一个普通的列表，但散布着一个 monad。你可以这样定义：transformersmtlmonat

import Control.Monad.Trans.Class (lift)
import qualified ListT -- from the list-t package
import ListT (ListT)

monat :: Monad m => Int -> ListT m Int
monat n = lift (return n) >>= \m -> cons m (monat (m + 1))

你可以像这样使用它：

ghci> ListT.toList (ListT.take 5 (monat 0) :: ListT Maybe Int)
Just [0,1,2,3,4]