Filtering a big list into the IO monad

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Filtering a big list into the IO monad

Gabriel Sztorc
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.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Filtering a big list into the IO monad

haskell-2
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...

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Filtering a big list into the IO monad

Udo Stenzel
In reply to this post by Gabriel Sztorc
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."

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Filtering a big list into the IO monad

Spencer Janssen
In reply to this post by Gabriel Sztorc
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 <[hidden email]> 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.
| _______________________________________________
| Haskell-Cafe mailing list
| [hidden email]
| http://www.haskell.org/mailman/listinfo/haskell-cafe
|
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe