populating a bloom filter; stymied by ST monad
I have a potentially very large number of values to feed into a bloom filter. They're coming from IO: getValues :: (v -> k -> k) -> k -> IO k getValues update initial = go initial =<< gen where go v [] = return v go v (f:fs) = do x <- val f go (maybe v (`update` v) x) fs gen = undefined val f = undefined This streams lazily, but if I build a list (getValues (:) []), the laziness is lost; the whole list is constructed and returned before any of it can be used. Which uses too much memory of course. So I can't use Data.BloomFilter.fromListB. Seems I need to do something like this: let filter = newMB (cheapHashes 13) 33554432 --- sized for 1 million items filter' <- unsafeFreezeMB <$> getValues insertMB filter Except this won't work, the mutable bloom filter uses the ST monad. And I cannot see a way to combine the three "MB" functions into a single computation in the same ST monad. Perhaps stToIO to is what I need, but I can't work out how to use it. Help? -- see shy jo
I mostly figured this out. stToIO allows converting (ST s a) to (IO a) and so I can update the bloom filter in IO. I do still wonder if there's a better way, avoiding modifying the filter inside IO and keeping it in ST. -- see shy jo
getValues update initial = go initial =<< gen where go v [] = return v go v (f:fs) = do You say that this stream lazily, so I deduce that gen produce a lazy IO list. So you should be able to use gen in conjunction with easyList to get your bloom filter lazily. I'm not sure what the problem is ? How exactly do you get the elements of your bloom filter from gen input ? -- Jedaï
Chaddaï Fouché wrote:
getValues update initial = go initial =<< gen where go v [] = return v go v (f:fs) = do x <- val f
You say that this stream lazily, so I deduce that gen produce a lazy IO list. So you should be able to use gen in conjunction with easyList to get your bloom filter lazily. I'm not sure what the problem is ? How exactly do you get the elements of your bloom filter from gen input ?
gen produces a lazy list, but it's then transformed using another IO operation. I added the relevant line back above. I did it that way to preserve laziness. An alternate, simpler getvalues suitable for easyList[1] would be the following, but due to the sequencing done by mapM, the list does not stream out lazily. getValues :: IO [v] getValues update initial = mapM val =<< gen -- see shy jo [1] If easyList didn't also destroy laziness by running length, anyway..
Hi, You can probably use some unsafeInterleaveIO to keep things lazier. Note that I am not actually suggesting this, an explicit streamy (iteratee, enumerator, conduit, pipes, ..) solution as suggested by others is probably superior. However I find that area too complicated for now and waiting for libraries to settle a bit. I'll give an example. How to incorporate this into your problem is up to you, if you ever want to do that. Try the following: import Control.Applicative import System.IO.Unsafe -- f is a weird function. it prints the result of a computation before returning it. f :: Show a => IO a -> IO a f i = do j <- i; print j; return j -- let's have an IO [Int] list to use in tests. xs :: IO [Int] xs = return [1..10] ghci> mapM f xs -- prints numbers from 1 to 10, and returns a list: [1..10] ghci> take 3 <$> mapM f xs -- prints numbers from 1 to 10, and returns a list: [1..3] What if we want to be 'lazier', only print those numbers that are in the output list? Albeit unsafe in certain cases, one way is the following: g :: Show a => IO a -> IO a g = unsafeInterleaveIO . f ghci> take 3 <$> mapM g xs -- prints numbers from 1 to 3 and returns a list [1..3] HTH, Ozgur On 13 March 2012 15:16, Joey Hess <joey@kitenet.net> wrote:
Chaddaï Fouché wrote:
getValues update initial = go initial =<< gen where go v [] = return v go v (f:fs) = do x <- val f
You say that this stream lazily, so I deduce that gen produce a lazy IO list. So you should be able to use gen in conjunction with easyList to get your bloom filter lazily. I'm not sure what the problem is ? How exactly do you get the elements of your bloom filter from gen input ?
gen produces a lazy list, but it's then transformed using another IO operation. I added the relevant line back above. I did it that way to preserve laziness. An alternate, simpler getvalues suitable for easyList[1] would be the following, but due to the sequencing done by mapM, the list does not stream out lazily.
getValues :: IO [v] getValues update initial = mapM val =<< gen
-- see shy jo
[1] If easyList didn't also destroy laziness by running length, anyway..
participants (3)
-
Chaddaï Fouché -
Joey Hess -
Ozgur Akgun