Filtra un elenco infinito di valori monadici

Question

Forse questo è ovvio, ma non riesco a capire come filtrare al meglio un elenco infinito di valori di I/O. Ecco un esempio semplificato:

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] 

Forse devo usare sequence in qualche modo, ma voglio la valutazione di essere pigro. Eventuali suggerimenti? L'essenza è che per ogni IO Int nell'output potremmo dover controllare diversi valori IO Int nell'input.

Grazie!

Answer 1

Non eseguibile senza utilizzare unsafeInterleaveIO o qualcosa di simile. Non è possibile scrivere un filtro con la seconda firma tipo, dal momento che se si potesse si potrebbe dire

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

Allo stesso modo, la prima firma di tipo non è andare a lavorare - ogni chiamata ricorsiva vi darà indietro qualcosa di digitare IO [a], ma per creare un elenco è necessario eseguire questa azione prima di restituire un risultato (poiché : non è in IO è necessario utilizzare >>=). Per induzione dovrai eseguire tutte le azioni nell'elenco (che impiega per sempre quando l'elenco è infinitamente lungo) prima di poter restituire un risultato.

unsafeInterleaveIO risolve questo problema, ma non è sicuro.

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 

il problema è che questo interrompe la sequenza che la monade dovrebbe fornire. Non hai più garanzie su quando accadono le tue azioni monadiche (potrebbero non accadere mai, potrebbero accadere più volte, ecc.).

Le liste semplicemente non funzionano con IO. Questo è il motivo per cui abbiamo la pletora di tipi di streaming (Iteratees, Conduit, Pipes, ecc.).

Il tale tipo più semplice è probabilmente

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

nota che noi osserviamo che

[a] == MList Id a 

dal

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) 

anche, MList è un funtore

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

ed è un funtore nella categoria delle trasformazioni di Functional e 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)) 

con questo è facile scrivere quello che volete

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 

o varie altre funzioni simili.