31–40 of 46 posts
When I first heard of Bloom filters, I thought of the Bloom effect - https://en.wikipedia.org/wiki/Bloom_(shader_effect) - and we used to call these things filters for a while - then friend of mine told me about the other meaning :)
Very similar with Shellsort, which was designed by Donald Shell.
Earlier quoted context omitted.
They both seem like fairly easy concepts. I'm not sure why they get so much coverage.
"A monad is just a monoid in the category of endofunctors, what's the problem?"
Can anyone tell me about a use case in game design?
This link[0] has an example; so basically almost anything in a game where it has to lookup massive amounts of data (e.g. logs), the example in the article is to quickly check if the user has already seen an item (in a game with thousands of items [e.g because those were pseudo-randomly generated, think RPGs]). But it's easy to think further applications: quickly check if the player already played this chess game befo…
Earlier quoted context omitted.
"A monad is just a monoid in the category of endofunctors, what's the problem?"
Wait. Is this true? If so, that's cool. I know your comment was sarcastic, but as a grad student in math I've futzed with category theory enough that those words mean more to me than the raw Kleisli triple definition.
Earlier quoted context omitted.
They both seem like fairly easy concepts. I'm not sure why they get so much coverage.
The problem is that Haskell developers like to push monads as the solution to a problem most developers in other languages don't actually have, so discovering the problem that's being solved is the difficult bit. Of course, this doesn't happen with other niche solutions because other niche solutions don't have an entire popular language which nearly-precisely encodes the problems monads are good at solving.
For instance, a pointer type in C is like a "Maybe a" in Haskell, because a pointer can always be null (Nothing).
Every month or so there is a new version of an article like this posted on hn
Earlier quoted context omitted.
The problem is that Haskell developers like to push monads as the solution to a problem most developers in other languages don't actually have, so discovering the problem that's being solved is the difficult bit. Of course, this doesn't happen with other niche solutions because other niche solutions don't have an entire popular language which nearly-precisely encodes the problems monads are good at solving.
It seems you're talking about the IO monad specifically, not about monads in general. Other monads, like Maybe and List, absolutely occur in programs written by "most developers in other languages", whether they perceive them as monads or not. For instance, a pointer type in C is like a "Maybe a" in Haskell, because a pointer can always be null (Nothing).
Bloom filters are a nice data structure, and you should absolutely have them in your toolbox, but if you go looking for a reason to use one you are likely to wind up making things worse. The following is not valid reasoning: "Bloom filters are efficient. Therefore if I can find a way to use a bloom filter, my solution will be efficient." The "SSH keys" protocol in the article seems like an example of this. It doesn't…
As much as the example is a bad one because it leaks server-side info to an unauthenticated client, I've had scenarios where if you have > 3 ssh keys in your key-chain all ssh login attempts fail after 3 keys are tried & cause failures. I end up writing ~/.ssh/config entries; a lot of them for the client to remember which key to try first.
My favourite real-life bloom-filter story is the "unsafe URLs" list that is in Chrome - the "Safe Browsing Bloom" is a neat way to send out obscured information about the bad URLs without actually handing out a list to a user. The web URLs or domains which find a match in this, do need to be checked upstream, but it avoids having to check for every single request with a central service.
On a similar note, been playing with a variant of bloom filters at work called a Bloom-1 filter [1] which works much faster than a regular bloom filter which has a lot of random memory access for 1 bit reads.
[1] - https://github.com/prasanthj/bloomfilter/blob/master/core/sr...
Bloom filters are a nice data structure, and you should absolutely have them in your toolbox, but if you go looking for a reason to use one you are likely to wind up making things worse. The following is not valid reasoning: "Bloom filters are efficient. Therefore if I can find a way to use a bloom filter, my solution will be efficient." The "SSH keys" protocol in the article seems like an example of this. It doesn't…
> "sort the hashes, and rice code the deltas"
Being quite sure that wasn't a racial slur, I looked it up:
> "Rice coding (invented by Robert F. Rice) denotes using a subset of the family of Golomb codes to produce a simpler (but possibly suboptimal) prefix code. Rice used this set of codes in an adaptive coding scheme; "Rice coding" can refer either to that adaptive scheme or to using that subset of Golomb codes." (https://en.wikipedia.org/wiki/Golomb_coding)
When I first heard of Bloom filters, I thought of the Bloom effect - https://en.wikipedia.org/wiki/Bloom_(shader_effect) - and we used to call these things filters for a while - then friend of mine told me about the other meaning :)
I think the first thing any article about Bloom filters should mention is that they were invented by a guy named Burton Bloom. They don't have anything to do with "blooming" of any sort. Very similar with Shellsort, which was designed by Donald Shell.
Thanks for the edification!!!