>И еще: все-таки нет никакого чисто функционального аналога для массивов и, соответственно, для хэш-таблиц. То есть нет структуры-словаря с временем доступа O(1) и временем записи элемента O(1).


Не для всякой хэш-таблицы выборка всегда O(1). Скорее наоборот -- это в случае массива выборка такая, потому как фактически адресная арифметика ;-)

Но вроде как ничего не мешает реализовать O(1) для чтения, даже в чистом функциональном (по-крайней мере на фон-неймановской архитектуре, какой-нибудь ad-hoc в компиляторе). С записью, разумеется не получится, ибо мутабельность. Но если не заморачиваться на чистоте то и запись, например используя ref в ML:

- val x = [ref 0];
> val x = [ref 0] : int ref list