Как нечисто изменить состояние, связанное с объектом?

Используя решение (1), мне удалось получить следующий дизайн. Во-первых, я добавил поле __lastAccessedBucket :: IORef Int в свой тип данных, как предложил @Xicò:

data Container a = Container { 
    length :: Int, 
    buffer :: V.Vector (Int,a), 
    __lastAccessedBucket :: IORef Int }

Затем мне пришлось обновить функции, создающие новый Container, чтобы создать новый IORef с использованием unsafePerformIO:

fromList :: [a] -> Container a
fromList list = unsafePerformIO $ do
    ref <- newIORef 0
    return $ Container (L.length list) buffer ref
    where buffer = V.fromList (prepare list)

Наконец, я создал две новые функции: findBucketWithHint, чистую функцию, которая выполняет поиск в корзине индекса с предположением (то есть в корзине, где, по вашему мнению, он может находиться), и функцию unsafeFindBucket, которая заменяет чистую findBucket, когда требуется производительность. всегда используя в качестве подсказки последнее доступное ведро:

unsafeFindBucket :: Int -> Container a -> Int
unsafeFindBucket findIdx container = unsafePerformIO $ do 
    let lastBucketRef = __lastAccessedBucket contianer
    lastBucket       <- readIORef lastBucketRef
    let newBucket     = findBucketWithHint lastBucket findIdx container
    writeIORef lastBucketRef newBucket
    return $ newBucket

Таким образом, unsafeFindBucket технически является чистой функцией с тем же API, что и исходная функция findBucket, но в некоторых тестах она на порядок быстрее. Я понятия не имею, насколько это безопасно и где это может привести к ошибкам. Темы, безусловно, вызывают беспокойство.

^{(Это больше расширенный комментарий, чем ответ.)}

Сначала я предлагаю проверить, не является ли это случаем преждевременная оптимизация. В конце концов, O(log n) не так уж и плохо.

Если эта часть действительно критична для производительности, ваше намерение определенно справедливо. Обычное предупреждение для unsafePerformIO: «Используйте его, только если вы знаете, что делаете», что вы, очевидно, делаете, и это может помочь сделать вещи чистыми и быстрыми одновременно. Убедитесь, что вы следуете всем меры предосторожности в документации, в частности установка правильных флагов компилятора (вы можете использовать прагму OPTIONS_GHC).

Также убедитесь, что операция IO является потокобезопасной. Самый простой способ убедиться в этом — использовать IORef вместе с atomicModifyIORef.

Недостатком внутреннего изменяемого состояния является то, что производительность кеша будет ухудшаться, если к нему обращаются из нескольких потоков, если они ищут разные элементы.

Одним из решений может быть явная передача обновленного состояния вместо использования внутреннего изменяемого состояния. Это, очевидно, то, чего вы хотите избежать, но если ваша программа использует монады, вы можете просто добавить еще один монадический слой, который внутренне сохранит состояние для вас, и выставит операцию поиска как монадическое действие.

Наконец, вы можете рассмотреть возможность использования отображаемых деревьев вместо массива. Вы по-прежнему будете иметь (амортизированную) сложность O(log n), но их большое преимущество заключается в том, что по замыслу они перемещают часто используемые элементы вверху. Таким образом, если вы будете обращаться к подмножеству элементов размером k, они вскоре будут перемещены наверх, поэтому операции поиска будут всего O(log k) (константа для одного, многократно используемого элемента). Опять же, они обновляют структуру при поиске, но вы можете использовать тот же подход с unsafePerformIO и атомарными обновлениями IORef, чтобы сохранить чистоту внешнего интерфейса.