Hi, Just a small comment on one of the comments. On 5/1/07, ajb@spamcop.net wrote:

Also, rather than this:

add :: Bloom a -> a -> Bloom a

a better argument order is this:

insert :: a -> Bloom a -> Bloom a

That way, you can use it with foldr.

Hmmm. If you want to create a Bloom using a fold wouldn't it make more sense to use foldl'? I think the argument order is fine. Cheers, Josef

Reminds me of this code from Data.Binary:

unroll :: Integer -> [Word8] unroll = unfoldr step where step 0 = Nothing step i = Just (fromIntegral i, i `shiftR` 8)

roll :: [Word8] -> Integer roll = foldr unstep 0 where unstep b a = a `shiftL` 8 .|. fromIntegral b

Which is a bit stream-fusion inspired, I must admit.

But better than what is in Codec.Utils:

toBase x = map fromIntegral . reverse . map (flip mod x) . takeWhile (/=0) . iterate (flip div x)

-- | Take a number a convert it to base n as a list of octets.

toOctets :: (Integral a, Integral b) => a -> b -> [Octet] toOctets n x = (toBase n . fromIntegral) x

powersOf n = 1 : (map (*n) (powersOf n))

-- | Take a list of octets (a number expressed in base n) and convert it -- to a number.

fromOctets :: (Integral a, Integral b) => a -> [Octet] -> b fromOctets n x = fromIntegral $ sum $ zipWith (*) (powersOf n) (reverse (map fromIntegral x))

It seems a shame that everyone has to roll their own. Dominic.

On Mon, 30 Apr 2007 ajb@spamcop.net wrote:

In bloom:

Function guards are your friends! This:

bloom hf sz hc = if condition then b else error "Badness"

is almost always better expressed as:

bloom hf sz hc | condition = b | otherwise = error "Badness"

Why replacing the almost-function 'if' by a special syntactic construct? Why replacing the two-branch decision 'if' by a multi-branch construct (similar to "switch") with two-branches? Express simple things the simple way!

Hi Andrew, Thanks for the comments, it really helps to have someone else's opinion on my code. I'll be applying what you've said as soon as I get a chance and I'm sure I'll have some more questions then. I'll certainly look more closely at the Set interface and try and duplicate all the parts which make sense. I've been using Darcs for a while with non-haskell projects as well as this project, however it seems that cabal strips out the darcs meta-data when making up a distribution tar file. Is there an option to have it include the darcs stuff? it seems like it could be quite useful and I can't really see a downside. If you're interested the Darcs repository is at: http://www.almostobsolete.net/bloom/ Tom On 5/1/07, ajb@spamcop.net wrote:

G'day.

Quoting tom :

...

I'm pretty new to Haskell, I've been working on a Bloom filter[1] implementation as a learning exercise.

Excellent! Sounds like a fun test.

...

I'd really appreciate it if someone more experienced would comment on the code. I'm sure there's plenty of places where I'm doing things in silly or overly complex ways.

Sure.

All in all, very well done. It works, and it looks pretty efficient. My quibbles are mostly stylistic or syntactic in nature. Please understand that the relative triviality of my quibbles is a sign that there are really no major problems.

This is not a criticism, but more an advertisement: What are you using for source control here? Darcs is nice, and as a bonus, it's trivially browsable from a web browser, which saves downloading and unpacking.

General comments:

You overuse parentheses. A lot. Definitions like this:

ary = (listArray (0, wordc-1) (repeat 0))

don't need parentheses around them, and just add to the general noise level.

And (.&. ((size b)-1)) is much more cleanly expressed as (.&. (size b - 1)).

Rather than carrying around a hash function, it might be better to use a type class:

class BloomHash k where bloomHash :: k -> [Word8]

In wordsize:

You don't need to hard-code this. You can use:

wordsize = bitSize (undefined::Word32) -- Or Int, of course!

bitSize is defined in Data.Bits.

In splitup:

I got a bit confused by the local binding names. It's usual, especially in generic code, to use "xs", "ys" etc for a list of "x" and "y". Something like this might be more idiomatic:

splitup n xs = let (xs1, xs2) = splitAt n xs in xs1 : splitup n xs2

In indexes:

(fromIntegral $ x `div` wordsize, fromIntegral $ x .&. (wordsize-1))

Seems intuitively wasteful. Either use divMod or bit operations.

Similarly, (hashfunc b) key is the same as hashfunc b key. But even better is:

split bytecount . hashfunc b $ key

That makes it obvious that it's a pipeline of functions applied to the key.

This looks cool:

bytes2int = foldr ((. (256 *)) . (+)) 0 . (map toInteger)

but I'm not smart enough to parse it. This is both more readable and shorter:

bytes2int = foldr (\x r -> r*256 + fromInteger x) 0

Integer log2's are probably better done using integers only, or at least abstracted out into a separate function.

In bloom:

Function guards are your friends! This:

bloom hf sz hc = if condition then b else error "Badness"

is almost always better expressed as:

bloom hf sz hc | condition = b | otherwise = error "Badness"

You can now inline b. (I can see why you put it in a where clause; now you don't have to.)

wordc, again, only needs integral arithmetic:

wordc = ceiling ((fromIntegral a) / (fromIntegral b :: Double))

is more or less:

wordc = (a+b-1) `div` b

And drop the parentheses around the definition of ary.

In add:

Try to use function names that are close to names in existing libraries, like Data.Set. "insert" sounds better here.

Also, rather than this:

add :: Bloom a -> a -> Bloom a

a better argument order is this:

insert :: a -> Bloom a -> Bloom a

That way, you can use it with foldr.

In test:

Again, probably misnamed. Data.Set calls this "member". And again, arguably the wrong argument ordering.

Once again, well done.

Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe