如何在 Haskell 中处理无限的 IO 对象列表？

Question

我正在编写一个从文件列表中读取的程序。每个文件要么包含到下一个文件的链接，要么标记它是链的末尾。

作为 Haskell 的新手，处理这个问题的惯用方法似乎是为此目的提供一个可能文件的惰性列表，到目前为止

getFirstFile :: String -> DataFile
getNextFile :: Maybe DataFile -> Maybe DataFile

loadFiles :: String -> [Maybe DataFile]
loadFiles = iterate getNextFile . Just . getFirstFile

getFiles :: String -> [DataFile]
getFiles = map fromJust . takeWhile isJust . loadFiles

，一切都很好。唯一的问题是，由于 getFirstFile 和 getNextFile 都需要打开文件，因此我需要将它们的结果放在 IO monad 中。这给出了修改后的形式

getFirstFile :: String -> IO DataFile
getNextFile :: Maybe DataFile -> IO (Maybe DataFile)

loadFiles :: String -> [IO Maybe DataFile]
loadFiles = iterate (getNextFile =<<) . Just . getFirstFile

getFiles :: String -> IO [DataFile]
getFiles = liftM (map fromJust . takeWhile isJust) . sequence . loadFiles

。问题在于，由于 iterate 返回一个无限列表，因此序列变成了无限循环。我不知道如何从这里继续。是否有一种更惰性的序列形式不会命中所有列表元素？我是否应该重新调整映射并 takeWhile 以便在每个列表元素的 IO monad 内进行操作？或者我是否需要放弃整个无限列表过程并编写一个递归函数来手动终止列表？

Answer 1

朝着正确方向迈出的一步

令我困惑的是getNextFile。和我一起进入一个简化的世界，我们还没有处理 IO。类型是Maybe DataFile ->也许是数据文件。在我看来，这应该只是 DataFile ->也许是DataFile，我会在这种调整可能的假设下进行操作。 这看起来很适合unfoldr。我要做的第一件事是制作我自己的 Expandr 简化版本，它不太通用，但使用起来更简单。

import Data.List

-- unfoldr :: (b -> Maybe (a,b)) -> b -> [a]
myUnfoldr :: (a -> Maybe a) -> a -> [a]
myUnfoldr f v = v : unfoldr (fmap tuplefy . f) v
  where tuplefy x = (x,x)

现在类型 f :: a ->也许 a 匹配 getNextFile :: DataFile ->也许 DataFile

getFiles :: String -> [DataFile]
getFiles = myUnfoldr getNextFile . getFirstFile

很漂亮，对吧？ unfoldr 很像 iterate，只不过一旦它命中 Nothing，它就会终止列表。

现在，我们有一个问题。 IO。我们怎样才能用 IO 来做同样的事情呢？甚至不要考虑“不得命名的函数”。我们需要一个增强的展开器来处理这个问题。幸运的是，unfoldr 的源代码< /a> 可供我们使用。

unfoldr      :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b  =
  case f b of
   Just (a,new_b) -> a : unfoldr f new_b
   Nothing        -> []

现在我们需要什么？健康剂量的IO。 liftM2 Expandr 几乎为我们提供了正确的类型，但这次不会完全削减它。

实际的解决方案

unfoldrM :: Monad m => (b -> m (Maybe (a, b))) -> b -> m [a]
unfoldrM f b = do
  res <- f b
  case res of
    Just (a, b') -> do
      bs <- unfoldrM f b'
      return $ a : bs
    Nothing -> return []

这是一个相当简单的转换；我想知道是否有一些组合器可以完成同样的任务。

有趣的事实：我们现在可以定义 unfoldr fb = runIdentity $unfoldrM (return . f) b

让我们再次定义一个简化的 myUnfoldrM，我们只需添加一个 liftM 在那里：

myUnfoldrM :: Monad m => (a -> m (Maybe a)) -> a -> m [a]
myUnfoldrM f v = (v:) `liftM` unfoldrM (liftM (fmap tuplefy) . f) v
  where tuplefy x = (x,x)

现在我们已经准备好了，就像以前一样。

getFirstFile :: String -> IO DataFile
getNextFile :: DataFile -> IO (Maybe DataFile)

getFiles :: String -> IO [DataFile]
getFiles str = do
  firstFile <- getFirstFile str
  myUnfoldrM getNextFile firstFile

-- alternatively, to make it look like before
getFiles' :: String -> IO [DataFile]
getFiles' = myUnfoldrM getNextFile <=< getFirstFile

顺便说一下，我使用 data DataFile = NoClueWhatGoesHere 以及 getFirstFile 和 getNextFile 的类型签名对所有这些进行了类型检查，并将它们的定义设置为未定义。

---

[edit] 更改了 myUnfoldr 和 myUnfoldrM 使其行为更像 iterate，包括结果列表中的初始值。

[编辑]关于展开的其他见解：

如果您很难理解展开，Collat​​z 序列 可能是最简单的例子之一。

collatz :: Integral a => a -> Maybe a
collatz 1 = Nothing -- the sequence ends when you hit 1
collatz n | even n    = Just $ n `div` 2
          | otherwise = Just $ 3 * n + 1

collatzSequence :: Integral a => a -> [a]
collatzSequence = myUnfoldr collatz

请记住，myUnfoldr 是“下一个种子”和“当前输出值”相同的情况下的简化展开，就像 collat​​z 的情况一样。考虑到 myUnfoldr 在 unfoldr 和 tuplfy x = (x,x) 方面的简单定义，这种行为应该很容易看出。

ghci> collatzSequence 9
[9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1]

---

更多，大多是不相关的想法

其余的与这个问题完全无关，但我就是忍不住沉思。我们可以用 myUnfoldrM 来定义 myUnfoldr：

myUnfoldr f v = runIdentity $ myUnfoldrM (return . f) v

看起来很熟悉吗？我们甚至可以抽象这个模式：

sinkM :: ((a -> Identity b) -> a -> Identity c) -> (a -> b) -> a -> c
sinkM hof f = runIdentity . hof (return . f)

unfoldr = sinkM unfoldrM
myUnfoldr = sinkM myUnfoldrM

形式的函数

sinkM 应该能够“下沉”（与“提升”相反）任何Monad m =>; 。 (a→mb)→一个-> m c 。

因为这些函数中的 Monad m 可以与 sinkM 的 Identity monad 约束统一。但是， 我没有看到任何sinkM实际上有用的东西。

Answer 2

sequenceWhile :: Monad m => (a -> Bool) -> [m a] -> m [a]
sequenceWhile _ [] = return []
sequenceWhile p (m:ms) = do
  x <- m
  if p x
    then liftM (x:) $ sequenceWhile p ms
    else return []

---

产量：

getFiles = liftM (map fromJust) . sequenceWhile isJust . loadFiles

Answer 3

正如您所注意到的，IO 结果不能是惰性的，因此您不能（轻松）使用 IO 构建无限列表。然而，有一个出路，在 unsafeInterleaveIO；有了这个，您可以执行以下操作：

ioList startFile = do
    v <- processFile startFile
    continuation <- unsafeInterleaveIO (nextFile startFile >>= ioList)
    return (v:continuation)

不过，这里要小心很重要 - 您只是将 ioList 的结果推迟到将来某个不可预测的时间。事实上，它可能永远不会运行。所以当你像这样聪明™时要非常小心。

就我个人而言，我只会构建一个手动递归函数。

Answer 4

惰性和 I/O 是一个棘手的组合。使用 unsafeInterleaveIO 是在 IO monad 中生成惰性列表的一种方法（这是标准 getContents、readFile 等使用的技术） 。然而，尽管这很方便，但它会将纯代码暴露给可能的 I/O 错误，并使释放资源（例如文件句柄）变得不确定。这就是为什么现在大多数“严肃”的 Haskell 应用程序（尤其是那些关心效率的应用程序）使用称为 Enumerators 和 Iteratees 的东西来进行流式 I/O。 Hackage 中实现这一概念的一个库是 enumerator。

您可能很乐意在应用程序中使用惰性 I/O，但我想我仍然会以此作为解决此类问题的另一种方法的示例。您可以在 此处 和 此处。

例如，您的数据文件流可以实现为枚举器，如下所示：

import Data.Enumerator
import Control.Monad.IO.Class (liftIO)

iterFiles :: String -> Enumerator DataFile IO b
iterFiles s = first where
    first (Continue k) = do
        file <- liftIO 
nbsp;getFirstFile s
        k (Chunks [file]) >>== next file
    first step = returnI step

    next prev (Continue k) = do
        file <- liftIO 
nbsp;getNextFile (Just prev)
        case file of
            Nothing -> k EOF
            Just df -> k (Chunks [df]) >>== next df
    next _ step = returnI step