haskell - 如何在 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 返回一个无限列表，因此序列变成了一个无限循环。我不知道如何从这里开始。是否有一种更惰性的序列形式不会命中所有列表元素？我是否应该重新调整 map 并 takeWhile 在每个列表元素的 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 做同样的事情？扔在那里？甚至不要考虑不应命名的函数。我们需要一个加强的展开器来处理这个问题。幸运的是，source for 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 sequence可能是最简单的例子之一。

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在这些功能中可以统一与Identity sinkM 的单子(monad)约束.但是，I don't see anything那sinkM实际上会有用。