如何在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返回一个无限列表,序列变成一个无限循环.我不知道怎么从这里开始.是否存在一种不会触及所有列表元素的更加懒惰的序列形式？我是否应该重新调整地图并在每个列表元素的IO monad中进行操作？或者我是否需要删除整个无限列表进程并编写递归函数来手动终止列表？

Answer 1

在正确方向迈出的一步

令我困惑的是getNextFile.和我一起进入一个简化的世界,我们还没有处理IO.类型是Maybe DataFile -> Maybe DataFile.在我看来,这应该只是DataFile -> Maybe DataFile,我将在假设这种调整是可能的情况下运作.而这看起来像一个很好的候选人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      :: (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

顺便说一句,我typechecked所有这些用data DataFile = NoClueWhatGoesHere,并为类型签名getFirstFile,并getNextFile与它们的定义设定undefined.

[edit]更改myUnfoldr并myUnfoldrM表现得更像iterate,包括结果列表中的初始值.

[edit]关于展开的其他见解:

如果你很难将头部展开,那么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和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]

更多,大多是无关的想法

其余的与这个问题完全无关,但我无法抗拒沉思.我们可以myUnfoldr用以下术语来定义myUnfoldrM:

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在那些函数中可以与Identitymonad约束统一sinkM.不过,我没有看到任何这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到将来某个不可预测的时间.事实上,它可能永远不会被运行.所以当你像这样聪明时,要非常小心.

就个人而言,我只想构建一个手动递归函数.