Purely Functional Data Structures (1996) [pdf]

It would be cool if someone could translate this into Typescript or the like, I think it would make it a lot more readable.

This has been a topic I've wanted to get into for a few years now, specifically because of Clojure! So if you have any additional recommendations I'd appreciate it.

I really enjoyed Friedman's book `Scheme and the Art of Programming` because it filled in some pieces missing from "The Little Schemer" (and "Seasoned Schemer"). Building stuff like `kons`, `map` and all that `letrec` stuff.

But the big difference between Scheme and Clojure is that in Scheme, while it's "functional by concept," you get to escape with `(set! ...)` whenever you want to have a more traditional ds/algo (like say doing the n queens problem).

In Clojure you can kind of do that by either escaping to Java, using protocols (with atoms), or using transients, but I often feel like there's a "more functional way to do stuff that hasn't been taught to me."

I've opened up either the Okasaki dissertation or book or both, but I've always had trouble reading it, and then sticking with it. And some stuff like looking at Rosetta code and saying "to reverse a linked list in a lisp is easy... because it's a cons cell" seems like cheating. Almost like showing up to an interview, saying your "linked list" is implemented in an array structure and then calling `reverse()` on it.

Will watch that talk from 2014, must not have seen it before.

I guess, conceptually, day to day things in Clojure does feel pretty natural, even easier, and I think I have a decent understanding of it. But then when I look at leetcode type problems, or something more involved, it takes a lot of mental effort to translate to it. Especially things like `big O` gets thrown away in my mental model. I get it, persistent data structures and all that, but there's still a mystery there.

What are software bugs that can be avoided by choosing data structures like these?

I'm making a broad, high-level presentation about immutability in technology. At my company we have folks who have heard of it in the context of ransomware-resilient backups, others who have heard of it in the context of infrastructure as code, and very few who have heard of it in terms of data structures (distributed and non-distributed). My goal is to showcase the concept in various contexts so that people can better understand its role as a key design choice in technology.

Personally I have no experience working on software that utilizes these, so if others here do, I would appreciate your input on how these make your software more reliable.

The emphasis on software reliability and bugs-avoided is because the audience works under the company's risk-management division.

Oh.. then, yes--this was unabashedly a (positively) triggered reaction (fortunately or unfortunately).

Purely functional data structures are very common in purely functional languages like Haskell but are also used in non functional languages via libraries like immutable.js.

At a high level, immutability forces you to be extremely deliberate about state changes in your application. This improves reasoning/understanding, reduces bugs, and eases debugging.

An example of immutability that you might be familiar with would be react props/state. You don’t modify your state. This makes reasoning about state much more simple.