On: Functional programming should be the future of sof...

[hither_shores]

> in pure FP either lookup or insert can be no better than O(log(n))

For single operations, yes. But what we really care about is usually the amortized performance over many operations, which can still be constant time.

[misja111 → hither_shores]

No, this is not the case. It is actually for non FP solutions that the amortized performance converges to constant time. But for pure FP, there is no solution that performs in constant time, also not when amortized.