Przefiltruj nieskończoną listę wartości monadycznych

Question

Być może jest to oczywiste, ale nie mogę wymyślić, jak najlepiej filtrować nieskończoną listę wartości we/wy. Oto uproszczony przykład:

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] 

Może muszę używać sequence w jakiś sposób, ale chcę ocena być leniwy. Jakieś sugestie? Istotą jest to, że na każdym wyjściu może być konieczne sprawdzenie kilku wartości IO Int na wejściu.

Dziękujemy!

Answer 1

Nie można tego zrobić bez użycia unsafeInterleaveIO lub czegoś w tym stylu. Nie możesz napisać filtr z drugim podpisem typu, ponieważ jeśli można można powiedzieć

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

Podobnie, pierwszy podpis typu nie będzie działać - każdy rekurencyjne wywołanie daje powrotem coś wpisz IO [a], ale następnie, aby zbudować listę z tego, musisz wykonać wykonać tę akcję przed zwróceniem wyniku (ponieważ : nie jest w IO, musisz użyć >>=). Przez indukcję będziesz musiał wykonać wszystkie akcje na liście (która trwa wiecznie, gdy lista jest nieskończenie długa), zanim możesz zwrócić wynik.

unsafeInterleaveIO rozwiązuje to, ale nie jest bezpieczne.

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 

Problem polega na tym, że łamie to sekwencję, którą monada ma zapewnić. Nie masz już gwarancji, kiedy dojdzie do monadycznych działań (mogą się one nigdy nie zdarzyć, mogą się zdarzyć wiele razy, itd.).

Listy po prostu nie grają dobrze z IO. Właśnie dlatego mamy mnóstwo strumieniowych typów (Iteratees, Conduits, Pipes, itp.).

Najprostszy taki typ jest prawdopodobnie

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

pamiętać, że widzimy, że

[a] == MList Id a 

od

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) 

również MList to funktor

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

i jest funktorem w kategorii transformacji Functor i 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)) 

z tym łatwo jest napisać co chcesz

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 

lub różne inne podobne funkcje.