1 post tagged “algorithms”

View other items tagged “algorithms:” Photos, Audio, Videos, Books or Links. View “algorithms” on Vox.

Pure Functional Disjoint Set Union-Find...

Jul 1, 2009
Post a comment

...is apparently not terribly efficient. This makes me sad. The problem doesn't seem like it should be as hard as it appears to be. This makes me more sad.

I've been doing a lot of pure functional programming. I wonder if I can discover a pure-functional union-find data structure with computational complexity similar to Tarjan's optimal imperative algorithm. Grmf.

Update: okay, I think I've convinced myself that purism really is a lost cause on this subject. How-some-ever, I've now written a persistent [impure] functional union-find data structure that I believe has optimal computational complexity. I'll post a follow-up.