Re:Binary Decision Diagrams (2010)
by iainmerrick on Wednesday December 09, 2020 @03:19PM
(#25364150)
Thank you! So I was looking at it from a purely functional point of view, without accounting for the earlier non-pure work in the literature. That makes sense; I was deep in the early Haskell world at the time.
> I’m not a Clojure expert, but I believe you could trace a direct line to Clojure’s core immutable data structures from Okasaki’s doctoral thesis.
I believe the direct inspiration for Clojure's persistent vectors and maps are Bagwell's papers on HAMTs, which weren't so much a new data structure as an example of data structure engineering. Okasaki's thesis has several contributions but its main theme is how you can apply amortization in the purely functional setting if you have laziness or memoization, which is in a very different direction.