过滤无限的monadic值列表

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应该提供的顺序.你不再保证你的monadic动作何时发生(它们可能永远不会发生,它们可能会发生多次,等等).

列表只是不喜欢IO.这就是我们拥有大量流媒体类型(Iteratees,Conduits,Pipes等)的原因.

最简单的这种类型可能是

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

或其他各种类似的功能.