A better example would be to implement an efficient HashMap in pure FP. This is simply impossible unless you fall back to some tree based solution which is less efficient.
Interested why this is downvoted .. Hashmaps can have O(1) time complexity for lookups and inserts in the imperative world, in pure FP either lookup or insert can be no better than O(log(n))
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.
