Хаскелл изменяемая структура кучи

Question

Я хочу создать структуру данных кучи. Также я хочу сделать операции с ним в монаде STM в многопоточном приложении. Кучи имеют размер 10 миллионов элементов. В куче много операций.

Я смотрел на эти пакеты

1. http://hackage.haskell.org/package/heap
2. http://hackage.haskell.org/package/heaps

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

Как мне кажется, мне нужно реализовать изменяемую кучу.

Я хочу услышать ваше мнение и совет, чтобы получить то, что я хочу.

Спасибо.

Answer 1

Как указывает Анкур, вы можете находиться за пределами чисто функциональной стороны Хаскелла. По крайней мере, я никогда не видел чистой структуры данных с минимальной выдержкой и хорошей производительностью памяти - не думайте, что ее нет. Вы профилировали существующие библиотеки, чтобы убедиться, что они не соответствуют вашим потребностям? (Помните, что постоянная структура данных не означает, что вся структура данных копируется всякий раз, когда производится мутация, может быть много совместного использования между различными "версиями").

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

Может быть сложно реализовать его так, чтобы он прекрасно работал с STM, основной концепцией которого является TVar. Вы могли бы основывать его на (даже не изменяемом) массиве TVars, но, поскольку каждая операция касается корня кучи, возникнет много споров, и издержки STM повредят вам. Я был бы более склонен сериализовать доступ к куче к одному потоку за раз, используя блокировки / MVars .

Я знаю Data.Vector.Mutable - это популярная библиотека изменяемых массивов. Другие будут более осведомлены, чем я, порекомендовав хорошую библиотеку изменяемых массивов для ваших целей.

Answer 2

В тот момент, когда вы начинаете мыслить в терминах «изменяемой области памяти» и «операций, которые изменяют эту область памяти», вы выходите за границы языков Pure FP, таких как Haskell, и все, что выходит за эти границы, потребует некоторые специальные приемы в хаскеле, такие как монады. В вашем случае изменяемой структуры данных вы пересекаете фундаментальную границу, которую я не уверен, может ли даже Монада помочь вам пересечь (монада может помочь вам смоделировать ее как изменяющуюся структуру данных, например: монаду состояния - но это не будет то, что вы ищете, так как вы хотите, чтобы оно было «изменчивым», а не просто симуляцией.