Filtering a big list into the IO monad
Hello, I want to filter a list with a predicate that returns a IO value, something that filterM is supposed to do. The problem is, filterM overflows the stack for really big lists and I couldn't come up with a simple replacement for filterM that would work for lists of any size (the truth is, I can't come up with anything at all :). The question is: how to do it? Any help is appreciated.
Gabriel Sztorc wrote:
Hello,
I want to filter a list with a predicate that returns a IO value, something that filterM is supposed to do. The problem is, filterM overflows the stack for really big lists and I couldn't come up with a simple replacement for filterM that would work for lists of any size (the truth is, I can't come up with anything at all :).
The question is: how to do it? Any help is appreciated.
What is the predicate computing? Does it have side effects? Does the order of evaluation matter? A dangerous solution is to use unsafeInterleaveIO or unsafePerformIO to change your predicate to look like a pure function...
Gabriel Sztorc wrote:
I want to filter a list with a predicate that returns a IO value, something that filterM is supposed to do. The problem is, filterM overflows the stack for really big lists
Are you sure it's filterM's fault? Can you post the code in question? Stack overflows are usually caused by too much lazyness, but for filterM that doesn't seem to make sense. Udo. -- <xinkeT> "Lord grant me the serenity to accept the things I cannot change, the courage to change the things I can, and the wisdom to hide the bodies of the people I had to kill because they pissed me off."
This message is literate Haskell source.
import System.IO.Unsafe (unsafeInterleaveIO)
First off, let's look at the code for filterM:
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM _ [] = return [] filterM p (x:xs) = do flg <- p x ys <- filterM p xs return (if flg then x:ys else ys)
The potential for a stack overflow is pretty obvious here. filterM is applied to the tail of the list before any result is returned. Here's a version that reverses the list as it filters. It will run in constant stack space.
filterRevM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterRevM p = flip go [] where go [] acc = return acc go (x:xs) acc = do flg <- p x if flg then go xs $! x:acc else go xs acc
And finally, here's a version that uses unsafeInterleaveIO, and if it isn't obvious, it really is unsafe! Please read up on the risks of unsafeInterleaveIO before using this version.
unsafeFilterIO :: (a -> IO Bool) -> [a] -> IO [a] unsafeFilterIO p [] = return [] unsafeFilterIO p (x:xs) = do flg <- p x ys <- unsafeInterleaveIO $ unsafeFilterIO p xs return (if flg then x:ys else ys)
Cheers,
Spencer Janssen
On 8/3/06, Gabriel Sztorc
participants (4)
-
Chris Kuklewicz -
Gabriel Sztorc -
Spencer Janssen -
Udo Stenzel