У меня есть постоянная структура данных hamt, основанная на отображенном хэшированном массиве tr ie, который является основой для нескольких более специфических c постоянных структур данных, например, таких как неизменяемый массив. Он предоставляет довольно простой API:
const hamtDel = (hamt, props, k) => {/* implementation */}
const hamtGet = (hamt, k) => {/* implementation */}
const hamtSet = (hamt, props, k, v) => {/* implementation */}
const hamtEmpty = () => {/* implementation */} // creates an empty hamt
hamt, k, v говорят сами за себя. props - это просто средство для добавления произвольных свойств в только что созданный объект hamt. Например, неизменяемый массив имеет дополнительные свойства length и offset, позволяющие выполнять эффективные операции cons и snoc.
hamt сам по сути является неупорядоченной картой. Так как заказанные Карты распространены в Javascript, я попытался реализовать одну из них на основе hamt. Однако это оказывается довольно сложно. Чтобы отследить порядок вставки, мне нужна hamt A для фактических пар ключ / значение, а также та, которая содержит отображение числа вставок на соответствующий ключ B.
Учитывая обе структуры, я могу получить доступ к элементам A как обычно и пройти A, получив порядок вставки, удерживаемый B. Однако, когда я хочу удалить элемент в A, мне также нужно удалить его в B. Ключи в B - количество вставок. Это означает, что в худшем случае мне придется пройти по всей структуре B, чтобы найти соответствующий ключ.
Третий hamt с инвертированными парами B может решить проблему, но в итоге три hamt s просто для того, чтобы получить заказанную Карту, кажется плохим выбором дизайна.
Я почти уверен, что эта проблема хорошо известна, и есть solid решения для ее решения. Я не нашел ничего полезного, так как мне не хватает соответствующей терминологии. Помощь по этому вопросу очень приветствуется.