7

也许这很明显，但我似乎无法弄清楚如何最好地过滤无限的 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输入中的几个值。

谢谢！

4

1 回答 1

11

不使用unsafeInterleaveIO或类似的东西是不可行的。您不能使用第二种类型签名编写过滤器，因为如果可以的话，您可以说

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

同样，第一个类型签名不起作用——任何递归调用都会给你返回 type 的东西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 配合使用。这就是为什么我们有过多的流类型（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)

它是函子和自然变换范畴中的函子。

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

或其他各种类似的功能。

于 2013-03-09T03:56:11.990 回答