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 <lispozord at gmail.com> wrote: | Hello, | |. | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe at haskell.org | |