过滤一元值的无限列表

Question

也许这是显而易见的，但我似乎无法弄清楚如何最好地过滤IO值的无限列表。下面是一个简单的例子：

infinitelist :: [IO Int] 

predicate :: (a -> Bool) 

-- how to implement this? 
mysteryFilter :: (a -> Bool) -> [IO a] -> IO [a] 

-- or perhaps even this? 
mysteryFilter' :: (a -> Bool) -> [IO a] -> [IO a] 

也许我以某种方式使用sequence，但我想评价偷懒。有什么建议么？其实质是，对于输出中的每个IO Int，我们可能必须检查输入中的几个IO Int值。

谢谢！

Answer 1

不使用unsafeInterleaveIO或类似的东西。你可以不写与第二类型签名的过滤器，因为如果你能，你可以说

unsafePerformIOBool :: IO Bool -> Bool 
unsafePerformIOBool m = case mysteryFilter' id [m] of 
    [] -> False 
    (_:_) -> True 

类似地，第一类型签名行不通的 - 任何递归调用都会给你回的东西键入IO [a]，但随后建立一个列表出来，你将需要执行这个动作在返回结果之前（因为:不在IO中你需要使用>>=）。通过归纳法，您必须在列表中执行所有操作（在列表无限长时需要永久​​执行），然后才能返回结果。

unsafeInterleaveIO解决此问题，但是不安全。

mysteryFilter f [] = return [] 
mysteryFilter f (x:xs) = do ys <- unsafeInterleaveIO $ mysteryFilter f xs 
          y <- x 
          if f y then return (y:ys) else return ys 

问题是，这打破了monad应该提供的顺序。你不再保证你的单调行动发生的时间（他们可能永远不会发生，他们可能会发生多次，等等）。

列表只是不和IO玩。这就是为什么我们有很多流式（迭代器，管道，管道等）。

最简单的这种类型的可能是

data MList m a = Nil | Cons a (m (MList m a)) 

需要注意的是，我们观察到

[a] == MList Id a 

因为

toMList :: [a] -> MList Id a 
toMList [] = Nil 
toMList (x:xs) = Cons x $ return $ toMList xs 

fromMList :: MList Id a -> [a] 
fromMList Nil = [] 
fromMList (Cons x xs) = x:(fromMList . runId $ xs) 

也MList是一个仿函数

instance Functor m => Functor (MList m) where 
    fmap f Nil = Nil 
    fmap f (Cons x xs) = Cons (f x) (fmap (fmap f) xs) 

它是Functor和Natural转换类中的一个函数。

trans :: Functor m => (forall x. m x -> n x) -> MList m a -> MList n a 
trans f Nil = Nil 
trans f (Cons x xs) = Cons x (f (fmap trans f xs)) 

与此很容易写你想要

mysteryFilter :: (a -> Bool) -> MList IO (IO a) -> IO (MList IO a) 
mysteryFilter f Nil = return Nil 
mysteryFilter f (Cons x xs) 
    = do y <- x 
     let ys = liftM (mysteryFilter f) xs 
     if f y then Cons y ys else ys 

或各种其他类似的功能是什么。