Patrick Thomson

Gosh, I have a few! Fistly, wavelet trees! Wavelet trees with something like RRR encoding for the bit vectors lets you work with massive datasets in positively tiny space and constant time. They're not even expensive to construct! My favorite introduction to the whole space of rank/select-friendly structures is Alex Bowe's tutorial: https://alexbowe.com/wavelet-trees/ I constantly agitate for people to realize that we now have an algorithm for O(n) generalized sorting. It's called discrimination sort, and while it's a complex subject its quite elegant once you internalize the algorithm. There's a talk by Prof. Henglein here: https://www.youtube.com/watch?v=sz9ZlZIRDAg 2017 saw the recommendation of a truly phenomenal approach to indexing data, using simple leaning structures. These indexes are poorly explored, there's still a ton of headroom here, but the paper is an incredibly cool read and very approachable: https://arxiv.org/abs/1712.01208 Another really cool family of algorithms and associated structures in distributed systems is CRDTs. They're poorly understood, but in research they have largely superseded operational transforms. The Wikipedia page branches off into lots of good research: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type If we slightly broadened the lens of what is an algorithm, my favoriate category-theoretic approaches to solving problems include Recursion Schemes which are a technique to totally separate the specification of…

This is a great paper, but I found it to be very challenging to read when I first ran into it, even though I had some experience programming in Haskell. As a one sentence pitch, this paper is to recursion what if and while are to goto. For a more detailed intro to the concepts see: https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.… If you are comfortable with Haskell, it should be relatively accessible. If you aren’t, but want a bit more flavor than my one sentence, the intro section in that blog post is still worth a read.

Not quite - think of the functor as a container for the recursive field, not the values attached to leaves. The leaf is your base recursive case and doesn't have a value to map over. Having your functor instance map over this recursive field is what allows you to write a non-recursive function that expects the field to have the already processed value from it's children! And yeah, the compiler can derive the functor instance! I don't know the mechanism for how it works but I think it might assume the last type parameter is the 'container' field (think the values in a list or maybe) It's not in the standard lib, but you can find a few implementations (it's usually called cata for catamorphism) available on hackage. I have used recursion-schemes and it works pretty well. I learned about this stuff via this excellent blog series: https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.…

I disagree somewhat, but I don't have time to write a detailed answer. Instead here's a quick sketch that is likely only intelligible if you have a fair bit of PLT background. The basic point is this: you don't need to teach "raw" recursion, just like you don't teach control-flow using goto. Just like structured programming introduced for/while/do loops to structure control flow, you can structure recursive programs into a few major groups. The most important one is good old structural recursion over algebraic data types. It's follows a very set formula, so there isn't much opportunity to go wrong. It helps to have pattern matching in your language to do this. This is the approach taken by How to Design Programs (http://htdp.org/) Example blog post you might read if you want to know more about the theoretical background: http://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/