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

Question

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

haskelliomonadsinfinite-looplazy-evaluation

8

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

作为 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单子中。这就给出了修改后的形式：

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返回一个无限列表，sequence变成了一个无限循环。我不确定该怎么继续下去。是否有一种更懒惰的序列形式，不会触及所有的列表元素？我应该重新调整map和takeWhile，使它们在每个列表元素内操作IO单子吗？还是我需要放弃整个无限列表过程，并编写一个递归函数来手动终止列表？

- rprospero

4个回答

10

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

- Thomas Eding

尝试谷歌搜索 takeWhileM，我发现了一个相关的问题，其中代码几乎与你的相同：https://dev59.com/qnNA5IYBdhLWcg3wAItP#1134212 - Rotsor

哈哈，说起来，我最近将monadlist包添加到了hackage。它有一个takeWhileM函数，带有(a -> m a) -> [a] -> m [a]的类型签名（当然，返回值更一般化，适用于MonadPlus）。我需要在其中添加我的sequenceWhile函数和sequenceWhileM函数（带有a -> m Bool的类型签名）。 - Thomas Eding

9

正如您所注意到的，IO结果无法懒加载，因此您无法（轻松地）使用IO构建无限列表。然而，有一种解决方法，在unsafeInterleaveIO中可以使用；通过这种方式，您可以做出以下操作：

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

在这里要非常小心，因为你刚刚推迟了ioList的结果到未来某个不可预测的时间。实际上，它可能永远都不会运行。因此，当你想要聪明地这样做时，请非常小心。

在我个人看来，我会构建一个手动递归函数。

- bdonlan

4

懒惰求值和I/O是一个棘手的组合。使用unsafeInterleaveIO可以在IO Monad中生成懒惰列表（这也是标准的getContents、readFile和类似函数所使用的技术）。虽然这很方便，但它会让纯代码面临可能的I/O错误，并使释放资源（如文件句柄）变得不确定。这就是为什么大多数“严肃”的Haskell应用程序（特别是那些关注效率的应用程序）现在使用称为Enumerators和Iteratees的东西进行流式I/O。Hackage上实现这个概念的库之一是enumerator。

您可能已经在应用程序中使用了懒惰I/O，但我想用这个作为解决这种问题的另一种方法的例子。您可以在这里和这里找到更深入的迭代器教程。

例如，您的DataFiles流可以像这样实现一个Enumerator：

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 $ getFirstFile s
        k (Chunks [file]) >>== next file
    first step = returnI step

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

- shang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dan Burton · Accepted Answer

迈出正确的一步

令我困惑的是getNextFile。让我们进入一个简化的世界，暂时不考虑 IO。这个类型是Maybe DataFile -> Maybe DataFile。我认为，它应该简化为DataFile -> Maybe DataFile，并且我将假设可以进行此调整。而这个函数看起来像是 unfoldr 的一个很好的候选。首先，我将制作一个简化版本的 unfoldr，它不太通用，但使用起来更加简单。

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 -> Maybe a 与 getNextFile :: DataFile -> Maybe DataFile 相匹配

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

很美，对吧？unfoldr与iterate非常相似，只是一旦遇到Nothing，它就会终止列表。

现在有一个问题，那就是IO。我们如何在其中加入IO并完成同样的事情呢？不要想着使用不能被命名的函数，我们需要一个强大的unfoldr来处理它。幸运的是，我们可以访问unfoldr的源代码。

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 unfoldr几乎可以得到正确的类型，但这次还不够。

一个实际的解决方案

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 f b = 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 的类型签名为 undefined。

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

[编辑] 解开展开的另一种方式:

如果您很难理解展开，科拉兹猜想可能是最简单的例子之一。

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是一种简化的展开函数，适用于“下一个种子”和“当前输出值”相同的情况，这就是collatz的情况。通过在unfoldr中定义myUnfoldr并使用tuplefy 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 -> m b) -> a -> m c 的函数，实现函数的“下沉”(相反于“提升”)。

因为这些函数中的 Monad m 可以与 sinkM 中的 Identity monad 约束统一。然而，我没有看到任何实际上可以使用 sinkM 的场景。