我如何处理Haskell中的IO对象的无限列表？ [英] How do I handle an infinite list of IO objects in Haskell?

问题描述

我正在编写一个从文件列表中读取的程序。每个文件都包含指向下一个文件的链接或标记它是链的末尾。

作为Haskell的新手，它似乎是处理此问题的惯用方法这是一个懒惰的列表可能的文件，为此，我有

  getFirstFile :: String  - > DataFile 
 getNextFile :: Maybe DataFile  - >也许DataFile 
 
 loadFiles :: String  - > [也许数据文件] 
 loadFiles =迭代getNextFile。只是。 getFirstFile 
 
 getFiles :: String  - > [DataFile] 
 getFiles =来自Just的地图。带着只是。 loadFiles 
  

到目前为止，这么好。唯一的问题是，因为getFirstFile和getNextFile都需要打开文件，所以我需要他们的结果在IO monad中。这给出了修改后的形式：

  getFirstFile :: String  - > IO DataFile 
 getNextFile ::可能DataFile  - > IO（也许DataFile）
 
 loadFiles :: String  - > [IO Maybe DataFile] 
 loadFiles = iterate（getNextFile =<<）。只是。 getFirstFile 
 
 getFiles :: String  - > IO [DataFile] 
 getFiles = liftM（地图来自Just。takeWhile isJust）。序列 。 loadFiles 
  

问题在于，由于迭代返回无限列表，所以序列变成无限循环。我不知道如何从这里开始。有没有一种懒惰的序列形式，不会击中所有的列表元素？我是否应该重新绘制地图，并在每个列表元素的IO monad内部进行操作？或者是否需要删除整个无限列表过程并编写一个递归函数来手动终止列表？

解决方案

向正确的方向迈进

让我感到困惑的是 getNextFile 。和我一起进入一个简化的世界，我们还没有处理IO。类型是也许DataFile - >也许DataFile 。在我看来，这应该只是 DataFile - >也许DataFile ，并且我将在假设这种调整是可能的情况下运行。 看起来像是 unfoldr 的好选择。我要做的第一件事就是制作我自己的简化版的unfoldr，这个版本不那么普遍，但使用起来更简单。

  import Data.List 
 
  -  unfoldr ::（b  - > Maybe（a，b）） - > b  - > [a] 
 myUnfoldr ::（a  - > Maybe a） - > a  - > [a] 
 myUnfoldr fv = v：unfoldr（fmap tuplefy。f）v 
其中tuplefy x =（x，x）
  

现在输入 f :: a - >也许匹配 getNextFile :: DataFile - >也许DataFile

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

美丽吧？ unfoldr 与 iterate 非常相似，除非它一次点击 Nothing ，它会终止列表。

现在，我们遇到了问题。 IO 。我们怎样才能用 IO 引发同样的事情呢？甚至不要认为关于不能命名的功能。我们需要一个更强大的未成年人来解决这个问题。幸运的是，来源为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 b 
 Just（a，b'） - > do 
 bs<  -  unfoldrM f b'
 return $ a：bs 
 Nothing  - > return [] 
  

这是一个相当直接的转换;有趣的事实：我们现在可以定义 unfoldr fb = runIdentity $ unfoldrM（return。）我们可以定义 unfoldr fb = runIdentity $ unfoldrM（return。 f）b

让我们再次定义一个简化的 myUnfoldrM ，我们只需要撒上在 liftM 中：

  myUnfoldrM :: Monad m => ; （a→m（可能a））→> a  - > m [a] 
 myUnfoldrM fv =（v :)`liftM` unfoldrM（liftM（fmap tuplefy）。f）v 
其中tuplefy x =（x，x）
  
 $ b现在我们都已经设定好了，就像以前一样。
 
 pre >  getFirstFile :: String  - > IO DataFile 
 getNextFile :: DataFile  - > IO（也许DataFile）
 
 getFiles :: String  - > IO [DataFile] 
 getFiles str = do 
 firstFile<  -  getFirstFile str 
 myUnfoldrM getNextFile firstFile 
 
  - 或者，使它看起来像$ b $之前b getFiles':: String  - > IO [DataFile] 
 getFiles'= myUnfoldrM getNextFile< =< getFirstFile 
  

顺便说一句，我使用 data来检查所有这些数据DataFile = NoClueWhatGoesHere 以及 getFirstFile 和 getNextFile 的类型签名，其定义设置为 undefined 。

---

[edit] changed myUnfoldr 和 myUnfoldrM 表现得更像 iterate ，包括结果列表中的初始值。

展开的其他见解：

如果您有困难的时刻将你的头围绕着展开，可能是最简单的例子之一。

  collat​​z :: Integral a => a  - >可能是
 collat​​z 1 = Nothing  - 当您按1 
 collat​​z n |时，序列结束即使n = Just $ n`div` 2 
 |否则=只需$ 3 * n + 1 
 
 collat​​zSequence :: Integral a => a  - > [a] 
 collat​​zSequence = myUnfoldr collat​​z 
  

记住， myUnfoldr 对于下一个种子和当前输出值相同的情况简化展开，就像collat​​z的情况一样。根据 unfoldr 和的简单定义，应该很容易看到 myUnfoldr tuplefy x =（x，x）。

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

---

更多，多数不相关的想法

其余与问题完全无关，但我无法抗拒沉思。我们可以根据 myUnfoldrM 定义 myUnfoldr ：

  myUnfoldr fv = runIdentity $ myUnfoldrM（return。f）v 
  

看起来熟悉？我们甚至可以抽象出这种模式：

  sinkM ::（（a  - > Identity b） - > a  - >身份c） - > （a  - > b） - > a  - > c 
 sinkM hof f = runIdentity。 hof（return。f）
 
 unfoldr = sinkM unfoldrM 
 myUnfoldr = sinkM myUnfoldrM 
  

$ b

















$ b

Monad m => （a - > m b） - > a - >因为这些函数中的 Monad m 可以与。





code>身份 sinkM 的monad约束。但是，我没有看到任何东西， sinkM 实际上会有用。

I'm writing a program that reads from a list of files. The each file either contains a link to the next file or marks that it's the end of the chain.

Being new to Haskell, it seemed like the idiomatic way to handle this is is a lazy list of possible files to this end, I have

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

So far, so good. The only problem is that, since getFirstFile and getNextFile both need to open files, I need their results to be in the IO monad. This gives the modified form of

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

The problem with this is that, since iterate returns an infinite list, sequence becomes an infinite loop. I'm not sure how to proceed from here. Is there a lazier form of sequence that won't hit all of the list elements? Should I be rejiggering the map and takeWhile to be operating inside the IO monad for each list element? Or do I need to drop the whole infinite list process and write a recursive function to terminate the list manually?

解决方案

A step in the right direction

What puzzles me is getNextFile. Step into a simplified world with me, where we're not dealing with IO yet. The type is Maybe DataFile -> Maybe DataFile. In my opinion, this should simply be DataFile -> Maybe DataFile, and I will operate under the assumption that this adjustment is possible. And that looks like a good candidate for unfoldr. The first thing I am going to do is make my own simplified version of unfoldr, which is less general but simpler to use.

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)

Now the type f :: a -> Maybe a matches getNextFile :: DataFile -> Maybe DataFile

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

Beautiful, right? unfoldr is a lot like iterate, except once it hits Nothing, it terminates the list.

Now, we have a problem. IO. How can we do the same thing with IO thrown in there? Don't even think about The Function Which Shall Not Be Named. We need a beefed up unfoldr to handle this. Fortunately, the source for unfoldr is available to us.

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

Now what do we need? A healthy dose of IO. liftM2 unfoldr almost gets us the right type, but won't quite cut it this time.

An actual solution

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 []

It is a rather straightforward transformation; I wonder if there is some combinator that could accomplish the same.

Fun fact: we can now define unfoldr f b = runIdentity $ unfoldrM (return . f) b

Let's again define a simplified myUnfoldrM, we just have to sprinkle in a liftM in there:

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)

And now we're all set, just like before.

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

By the way, I typechecked all of these with data DataFile = NoClueWhatGoesHere, and the type signatures for getFirstFile and getNextFile, with their definitions set to undefined.

---

[edit] changed myUnfoldr and myUnfoldrM to behave more like iterate, including the initial value in the list of results.

[edit] Additional insight on unfolds:

If you have a hard time wrapping your head around unfolds, the Collatz sequence is possibly one of the simplest examples.

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

Remember, myUnfoldr is a simplified unfold for the cases where the "next seed" and the "current output value" are the same, as is the case for collatz. This behavior should be easy to see given myUnfoldr's simple definition in terms of unfoldr and 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]

---

More, mostly unrelated thoughts

The rest has absolutely nothing to do with the question, but I just couldn't resist musing. We can define myUnfoldr in terms of myUnfoldrM:

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

Look familiar? We can even abstract this pattern:

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 should work to "sink" (opposite of "lift") any function of the form

Monad m => (a -> m b) -> a -> m c.

since the Monad m in those functions can be unified with the Identity monad constraint of sinkM. However, I don't see anything that sinkM would actually be useful for.

这篇关于我如何处理Haskell中的IO对象的无限列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！