The joy of recursion, immutable data, & pure functions: Making mazes with JS
11 comments
·August 18, 2025tikhonj
If you enjoyed that, I have a blog post on generating mazes in Haskell (from over a decade ago!). The algorithm is very similar, but the code is written using "inductive graphs" and the post is really more of an intro to working with graphs in a purely functional style.
chowells
I'm slightly horrified by the memory leak that's casually introduced without even a remark as to the potential to cause a problem. I can't tell if I'm more horrified by the cavalier attitude or the fact that JavaScript makes having a global registry the only easy way to use an object of an arbitrary type as a key to Map.
But at the very least, if you're going to memoize immutable values, please do it in a way that allows garbage collection. JavaScript has WeakRef and FinalizationRegistry. (Why it doesn't provide the obvious WeakCache built on those is a mystery, though.)
The issues won't be visible on a toy example like making mazes a few hundred elements across, but if you use these techniques on real problems, you absolutely need to cooperate with the garbage collector.
b_e_n_t_o_n
Probably better to use an LRU cache rather than weak maps.
sltkr
No because then you lose the ability to compare objects for equality.
hombre_fatal
Nice animation on the maze building algo.
I remember trying to use Immutable.js back in the day. It's probably pretty great with Typescript these days, but I remember it was kinda hell with vanilla JS back then since I'd accidentally do things like assign `thing.foo = 42` instead of `thing.set('foo', 42)` and I'd comb through the code to see why it wouldn't work, and I remember not knowing when I had a JS object or a Record. All things fixed by Typescript, of course.
sillysaurusx
I’m still sad that JS doesn’t have tail call optimization. I’ve always wondered why. Is it hard to implement?
zdragnar
If my memory serves right, the browser vendors couldn't agree on the implementation.
On the one hand, allowing any function to be eligible for TCO means that the developer won't know if the code was optimized or not. A trivial change can easily convert a fast function to one that blows the stack. Additionally, every function created- or at least every named function- would need to be analyzed, causing a performance hit for everyone, even those who never write a recursive function in their lives.
On the hand, some argued that TCO eligibility should be explicitly opt-in with some sort of keyword or annotation. If a function so annotated did not end up being a valid target for TCO, the script would not compile, similar to a syntax error. This is an even more harsh failure mode than the implicit version, but would have been easier to identify.
I vaguely recall chrome devs generally being in favor of explicit annotations, and Safari implicit. I could be completely wrong on this, and I don't think anyone was particularly enthused about the trade-offs either way.
chowells
People are too addicted to automatic stack traces for mainstream languages to optimize away stack frames.
Jtsummers
It does if you use JavaScriptCore (Safari, other Webkit browsers, Bun).
jefecoon
Nice read, and beautiful website btw.
Kind of amusing and maybe telling that this article about implementing an algorithm functionally begins by explaining it in an iterative, mutational fashion.