過濾一元值的無限列表

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 

或各種其他類似的功能是什麼。