Спецификация проблемы:
В настоящее время я ищу элегантное и/или эффективное решение проблемы, которая, как мне кажется, довольно распространена. Рассмотрим следующую ситуацию:
Я определил fileformat на основе BTree, который определен (упрощенным способом) следующим образом:
data FileTree = FileNode [Key] [FileOffset]
| FileLeaf [Key] [Data]
Чтение и запись этого из файла в ленивую структуру данных реализовано и работает нормально. Это приведет к экземпляру:
data MemTree = MemNode [Key] [MemTree]
| MemLeaf [Key] [Data]
Теперь моя цель состоит в том, чтобы иметь общую функцию updateFile :: FilePath -> (MemTree -> MemTree) -> IO ()
, которая будет читаться в FileTree
и преобразовать ее в MemTree, применить функцию MemTree -> MemTree
и записать изменения в древовидную структуру. Проблема в том, что FileOffsets должны быть сохранены каким-то образом.
У меня есть два подхода к этой проблеме. У обоих из них нет элегантности и/или эффективности:
Подход 1: Расширьте MemTree, чтобы содержать смещения
Этот подход расширяет MemTree, чтобы содержать смещения:
data MemTree = MemNode [Key] [(MemTree, Maybe FileOffset)]
| MemNode [Key] [Data]
Затем функция чтения будет считываться в FileTree
и сохраняет FileOffset
вместе с ссылкой MemTree
. Запись будет проверять, имеет ли ссылка уже связанное смещение, и если оно просто использует его.
Плюсы: легко реализовать, нет накладных расходов, чтобы найти смещение
Минусы: предоставляет внутреннюю информацию пользователю, который отвечает за установку смещения на Nothing
Подход 2: сохранение смещений во вторичной структуре
Другой способ атаковать эту проблему - прочитать в FileTree
и создать StableName.Map
, который хранится на FileOffsets
. Таким образом (и если я правильно понимаю семантику StableName
), можно взять окончательный MemTree
и найти StableName
каждого node в StableName.Map
. Если есть запись, node является чистой и ее не нужно писать снова.
Плюсы: не выставляет внутренности пользователю
Минусы: включает накладные расходы для поиска на карте
Заключение
Это два подхода, о которых я могу думать. Первый должен быть более эффективным, второй - более приятным для глаз. Я бы хотел, чтобы ваши комментарии к моим идеям, может быть, у кого-то даже есть лучший подход в виду?
[Edit] Reasonal
Есть две причины, по которым я ищу решение, подобное этому:
С одной стороны, вы должны попытаться обработать ошибки до их возникновения, используя систему типов. Вышеупомянутый пользователь, конечно, является разработчиком следующего слоя в системе (т.е. меня). Работая над представлением чистого дерева, некоторые виды ошибок не смогут произойти. Все изменения в дереве файла должны быть в одном месте. Это должно облегчить рассуждения.
С другой стороны, я мог бы просто реализовать что-то вроде insert :: FilePath -> Key -> Value -> IO ()
и сделать с ним. Но тогда я потеряю очень приятную черту, которая будет бесплатной, когда я сохраню (вроде) журнал, обновив дерево на месте. Транзакции (т.е. Слияние нескольких вставок) - это всего лишь работа над одним и тем же деревом в памяти и запись различий обратно в файл.