Ask HN: What elegant concepts (like recursion) should others be exposed to?
I'm studying state machines right now and I find the model for describing systems of change very interesting. State machines remind me of the _smell_ of recursion. They are are very powerful, yet rather simplistic in their most fundamental form, but have deep properties and far reaching application in problem solving. What are some other constructs that others may not be aware of (they don't need to be mathematical or specifically related to problem solving for that matter) that you find interesting?
2 comments
[ 8.0 ms ] story [ 17.8 ms ] threadContinuations.
Why people love Erlang.
The reasons why Erlang is rarely used in practice.
Software rasterization.
Disruptor pattern.
van Emde Boas Trees: A tree structure which supports some heap operations (insert/extract-min) in O(lglg n) time using some nice storage and recursive tricks. I actually just wrote this up in Java and I'd be happy to throw it on Github if there is any interest. I found the chapter on these in Cormen's Introduction to Algorithms rather daunting and confusing so I'd look for other sources to get a good grasp on it.
Randomized data structures/algorithms: The use of randomization to achieve expected run-times where the worst-case is extremely pessimistic such as in randomized Quicksort to get an expected O(nlgn) bound, along with using the median of medians algorithm (another elegant recursive trick/analysis to prove an O(n) bound) for picking a pivot. Random hash tables and the proofs in number theory for building a 'universal' hash function using mod arithmetic to avoid collisions.