Is purely functional programming in some situations less efficient than imperative programming?

Question

I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that some of the data types don't exist in functional languages. For example, it may be hard to implement hash data structures or mutable arrays.

With that in mind, is purely functional programming in some situations algorithmically more expensive than imperative programming? For example,

• If I want to implement timer heap with O(1) peeking of next timer to expire, O(log N) removal of next timer to expire, O(log N) addition of new timer, O(log N) removal of arbitrary timer and O(log N) adjustment of timer expiration time, can I implement the timer heap in a purely functional programming language?
• If I want to implement a timer wheel, can I do so in a purely functional programming language?
• If I want to implement O(1) lookup in a set or a map, meaning in practice hash structures are needed, can I do so in a purely functional programming language?
• If I want to implement a ring buffer for efficient communication between threads in a producer-consumer pattern, can I do so?
• If I want to maintain a a list of free TCP ports in a firewall, doubly linked list would be a suitable O(1) data structure for that, allowing O(1) removal of an arbitrary port, but can I do so in a purely functional language?
• If I want to have a fast and efficient O(1) bit set, can I have such a construct in a purely functional language?

Note I'm not interested in large vs small constant in the runtime. I'm interested in runtime becoming fundamentally different, e.g. O(log N) instead of O(1). Of course functional algorithms may be less efficient due to the extra overheads of added abstraction in terms of runtime constant.

Answer 1

Yes. There are problems where we can prove there is a $\Omega(\lg \lg n)$ factor slowdown. We also know that the slowdown is at most $O(\lg n)$ in all cases. See What classes of data structures can be made persistent?.

Answer 2

Another answer is that imperative (updatable) data structures can be used in pure functional program via monads (such as Haskell ST monad) or unique types (in Clean).