懒列表包装在IO中

Question

假设这段代码：

f :: IO [Int]
f = f >>= return . (0 :)

g :: IO [Int]
g = f >>= return . take 3

当我在ghci中运行g时，它会导致stackoverflow。但是我想也许它可以被惰性地评估并生成包含[0, 0, 0]的IO。我怀疑是IO的问题，但我真的不知道。显然以下代码可以工作:

f' :: [Int]
f' = 0 : f'

g' :: [Int]
g' = take 3 f'

---

编辑：实际上我对于这样一个简单的函数 f 不感兴趣，原始代码看起来更像是这样：

h :: a -> IO [Either b c]
h a = do
    (r, a') <- h' a
    case r of
        x@(Left  _) -> h a' >>= return . (x :)
        y@(Right _) -> return [y]

h' :: IO (Either b c, a)
-- something non trivial

main :: IO ()
main = mapM_ print . take 3 =<< h a

h执行一些IO计算，并将无效（Left）响应存储在列表中，直到产生有效响应（Right）。尝试懒惰地构建列表，即使我们在IO单子中也是如此。因此，读取h的结果的人甚至可以在完成之前开始消耗列表（因为它甚至可能是无限的）。如果读取结果的人只关心前三个条目，那么甚至不需要构造列表的其余部分。我感觉这似乎是不可能的 :/。

- jakubdaniel

---

h'会调用h吗？你能展示一下真正的代码吗？你希望它只执行足够产生需求结果的IO，还是无论如何都要全部执行？ - dfeuer

只需生成所需的结果，实际代码要大得多且混乱得多，但我仍然相信当我粘贴简化版本时会有所帮助。h不是从h'中调用的。 - jakubdaniel

我犯了些错误，我应该睡一晚再回来看。 - jakubdaniel

啊，如果你想让评估驱动执行，unsafeInterleaveIO 是你唯一的选择。 - dfeuer

Answer 1

是的，这里应该归咎于IO。对于IO的>>=操作符在"世界状态"方面是严格的。如果你写m >>= h，那么你将得到一个动作，首先执行动作m，然后将h应用于结果，最后执行h产生的动作。你的f动作不管有没有"做什么"都没关系，它必须被执行。因此，你会陷入一个无限循环，一遍又一遍地开始f动作。

幸运的是，有一种方法可以解决这个问题，因为IO是MonadFix的一个实例。你可以"神奇地"从该动作中访问IO动作的结果。至关重要的是，这种访问必须足够懒惰，否则你会陷入无限循环。

import Control.Monad.Fix
import Data.Functor ((<$>))

f :: IO [Int]
f = mfix (\xs -> return (0 : xs))

-- This `g` is just like yours, but prettier IMO
g :: IO [Int]
g = take 3 <$> f

甚至在GHC中为此提供了一些语法糖，让您可以使用rec关键字或mdo符号来使用do符号。

{-# LANGUAGE RecursiveDo #-}

f' :: IO [Int]
f' = do
  rec res <- (0:) <$> (return res :: IO [Int])
  return res

f'' :: IO [Int]
f'' = mdo
  res <- f'
  return (0 : res)

如果您想了解更多有关如何使用MonadFix的有趣示例，请参阅Haskell Wiki。

- dfeuer

---

我可能过于简化了某些事情，我会编辑原始帖子。 - jakubdaniel

Answer 2

听起来你想要一个混合了列表和IO能力的单子。幸运的是，这正是ListT的用途。以下是你的例子，采用该形式并且有一个h'函数，它可以计算Collatz序列并询问用户对序列中每个元素的感觉（我无法想到任何符合你提纲的说服性内容）。

import Control.Monad.IO.Class
import qualified ListT as L

h :: Int -> L.ListT IO (Either String ())
h a = do
  (r, a') <- liftIO (h' a)
  case r of
    x@(Left  _) -> L.cons x (h a')
    y@(Right _) -> return y

h' :: Int -> IO (Either String (), Int)
h' 1 = return (Right (), 1)
h' n = do
  putStrLn $ "Say something about " ++ show n
  s <- getLine
  return (Left s, if even n then n `div` 2 else 3*n + 1)

main = readLn >>= L.traverse_ print . L.take 3 . h

这是在ghci中的样子:

> main
2
Say something about 2
small
Left "small"
Right ()
> main
3
Say something about 3
prime
Left "prime"
Say something about 10
not prime
Left "not prime"
Say something about 5
fiver
Left "fiver"

我认为现代方法会使用管道或者迭代器等，但是我对它们不够了解，无法与ListT进行比较。

- Daniel Wagner

---

有可能有一天这个 ListT 会取代 transformers 中的那个吗？ - jakubdaniel

我能否以任何方式将ListT IO（Either a b）懒惰地转换为IO [Either a b]，以便我不必用ListT的东西来污染调用者？ 我本来希望toList是懒惰的，但似乎并不是:/ 我还希望选择使用take 3还是仅使用identity，因此我希望流可能是无限的。 - jakubdaniel

@JakubDaniel 在上述 main 的定义中，你当然可以将 id 替换为 take 3，没问题。的确 toList 并不像惰性 IO 那样是延迟计算的 -- 你应该把这视为另一种好处，原因我在另一个答案中已经概述了。在调用 toList 之前，你需要决定是否想要调用 take 3 或者 id。然而，toList 的确是将 ListT IO (Either a b) 转化为 IO [Either a b] 的正确方法。 - Daniel Wagner

是的，但如果我选择id，那么当函数不终止时，严格性会导致我无法读取中间结果:( 这违背了使用ListT而不是正常列表的目的，就像我编辑原问题所示。通常情况下，函数无法终止。 - jakubdaniel

@JakubDaniel 这不正确：正如我的示例所示，您可以使用traverse_在可用时检查中间值。 - Daniel Wagner

Answer 3

我不确定这是否是适当的使用方式，但是unsafeInterleaveIO可以让你获得所需的行为，通过推迟f中的IO操作，直到要求f内部的值：

module Tmp where
import System.IO.Unsafe (unsafeInterleaveIO)

f :: IO [Int]
f = unsafeInterleaveIO f >>= return . (0 :)

g :: IO [Int]
g = f >>= return . take 3

*Tmp> g
[0,0,0]

- amalloy

---

这似乎解决了问题，谢谢。使用它有什么缺点吗？名称并不是很让人放心 ;)。 - jakubdaniel

嗯，这就是为什么我说我不确定这是否合适。unsafeInterleaveIO有时可以使用，但通常很危险；找一个比我更有经验的人告诉你这是否是个好主意。 - amalloy

缺点在于它会破坏你对 IO 发生的直觉：通常，在 m >>= f 中，我们希望 m 的 IO 在将参数应用于 f 之前发生；但是，在 unsafeInterleaveIO m >>= f 中，m 的 IO 将被延迟。将其翻译到您的问题上下文中，这意味着 h 的列表的消费者决定执行哪些（如果有！）h' 迭代。这也容易受到编译器优化的影响。因此，如果您正在进行需要关注发生的 IO（几乎总是如此）的操作，则这是一个非常糟糕的想法！ - Daniel Wagner