Ask HN: What are some cool but obscure data structures you know about?

Bitboards for chess board representation, the fastest and most complex such representation: https://www.chessprogramming.org/Bitboards Other structures for chess are easier to follow and understand: https://www.chessprogramming.org/Board_Representation

Firstly, accessing an arbitrary list index is O(N), whilst a Zipper can access its focus in O(1) (shifting the focus is O(1) for both Zippers and list+index)

Secondly, using an index forces us to do bounds checks, keep track of the length (or re-calculate it at O(N) cost), etc. whereas a Zipper is "correct by construction"; i.e. every value of type (List[A], A, List[A]) makes sense as a zipper; whereas many values of type (List[A], Nat) don't make sense as zippers; e.g. ([], 42) doesn't make sense. Our logic also becomes easy for pattern-matching, e.g. in Scala:

    myZipper match {
      case Zipper(xs, x, y::ys) => Zipper(x::xs, y, ys)
      case z => z
    }

Also, your example of 'list[index-1]' is more complicated than it first appears. In particular, what is the type of 'index'? If it's an integer, then at least half of the possible values are meaningless (negative numbers); if its a natural (AKA unsigned integer), then it's not closed under subtraction (i.e. we have to worry about underflow)!

Thirdly, Zippers can be unbounded in both directions (i.e. the lists can be "infinite"/co-inductive). For example, they're great for implementing Turing machines, starting with an infinite blank tape in both directions. https://en.wikipedia.org/wiki/Coinduction

Fourthly, Zippers have more sharing. Here's an arbitrary example: say we have a zipper like this:

    ([c, b, a, ...], elem, [x, y, z, ...])

If we shift right, replace the focused element with 'newElem', then shift right again, we'll get this zipper:

    ([newElem, elem, c, b, a, ...], y, [z, ...])

Those operations take O(1) time and O(1) memory (and produce O(1) garbage, if we're no longer using the old zipper). In particular, since the tails of the lists ([c, b, a, ...] and [z, ...]) are unchanged, the same pointers will appear in both the old and new zippers; there has been no copying. This is important, since those lists could be arbitrarily long (or infinite!).

In contrast, if we did these operations on a list+index, everything before the replaced element would need to be reallocated; i.e. [..., a, b, c, elem, _] would need to be copied, since _ has changed from 'y, z, ...' to 'newElem, z, ...'. That requires O(N) memory allocation, takes O(N) time to do the copying (and produces O(N) garbage, if we don't want the old zipper).

> ...bloom filters... Good use-case: routing. Say you have a list of 1 million IPs that are black listed...

Seems-needed clarification: Bloom filters suffer from false positives, but not false negatives. So - if BloomFilterBlacklistCheck( $IP ) returns false, your router can safely conclude "not blacklisted". But if it returns true, then you'll need to perform further checks. (And you can't just use a Bloom filter of known false positive - that will also suffer from false positive, potentially letting in traffic from blacklisted IPs.)

Bitboards, although perhaps not so obscure, allow for some very nice optimization tricks.

I've used them to solve Sudoku puzzles really fast.

arrays are pretty underground, theyre like lists but better. C++ offers arrays but unfortunately python doesnt :(