Реализация эффективной структуры данных на молнии в Haskell с доступом к O (1) элементам

Question

Реализация эффективной структуры данных на молнии в Haskell с доступом к O (1) элементам

Вопрос

Я хочу создать тип данных, который обеспечит быстрый доступ и модификацию его элементов. Можно ли создать в Haskell структуру и функции, которые будут работать так же быстро, как и простая реализация C ++?

Детали проблемы

Я пишу компилятор в Haskell. у меня есть АСТ представленный типом данных, давайте рассмотрим следующий:

import Prelude hiding (id)

-- this is a sample data type, the real one has got a lot of constructors
data AST = A { id :: Int, x :: AST, y :: AST, z :: AST }
| B { id :: Int }
| C { id :: Int, x :: AST, y :: AST }
| D { id :: Int, u :: AST, v :: AST, w :: AST}

Каждый узел AST имеет уникальный идентификатор. Я хотел бы реализовать в Haskell следующие функциональные возможности:

функция getById, который вернет AST-узел выбранного идентификатора в O(1) сложность времени.
уметь создавать «фокусы» на структуре и изменять сфокусированные элементы независимо друг от друга. Поэтому я хотел бы иметь возможность помнить фокусы на некоторых поддеревьях и иметь возможность изменять каждый такой фокус в O(1) сложность времени.

Я думал о Молнии, но есть 3 проблемы с ними:

Они используются (насколько я знаю) с простыми типами данных, такими как двоичные деревья, где мы можем сказать, что мы выбираем «левую» или «правую» ветвь. Есть ли какой-нибудь простой способ использовать их для сложных типов данных, подобных приведенному выше?
Я думаю, что они не позволят мне реализовать функцию getById с O(1)сложность времени, я прав?
Я думаю, что невозможно создать несколько независимых фокусов, используя молнии. Под независимыми фокусами я подразумеваю фокусы, которые позволят нам изменять различные части типа данных без необходимости пересчета других фокусов (в O(1)).

Образ мышления С ++

В C ++ мы могли бы создать массив указателей на узлы AST nodePtrs, Функция nodeById будет выполнять в O(1), просто получив доступ *(nodePtrs[id]), Поскольку структура C ++ изменчива, мы могли бы изменять ее элементы без каких-либо ограничений в O(1),

4

algorithm c++haskell performance zipper

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я думаю, что молнии на самом деле всегда доступны, вы слышали о дифференциация?

Ну о getByIdЯ не уверен, что это хорошая идея. Вы, вероятно, хотите функцию Haskell, как getById :: Int -> IO AST который использует поиск в массиве или что-то. Но так как вы позже захотите иметь возможность изменять значения (по крайней мере, концептуально), вы хотите getById вернуть новые измененные значения AST или первое сохраненное значение AST? Это все становится проблематичным. Было бы неплохо проверить, можете ли вы просто удалить идентификаторы для своей версии на haskell.

Я думаю, что ваши фокусы звучат выполнимо. Если мы говорим, что ZAST это тип данных молнии для AST. Тогда вы, возможно, могли бы иметь что-то вроде.

makeFocus :: ZAST -> Focus ZAST

type Focus =
(ZAST -> ZAST) -> -- The modifier of the "below part"ZAST ->           -- The new "above part", you have to provide it again as it might have changed
ZAST              -- The Result

Но да, это не так удобно, как в C ++.

В заключение, я думаю, вы должны сделать шаг назад и посмотреть, можно ли эффективно выполнить то, что вы на самом деле пытаетесь сделать (оптимизация AST, генерация сборок и т. Д.) С неизменяемыми структурами данных. Вместо того, чтобы сосредоточиться на попытках достичь тех же спецификаций изменяемой структуры данных C ++ в Haskell.

1