Наложить структуру данных? - PullRequest
Новая
       15

Наложить структуру данных?

8 голосов
/ 11 июня 2011

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

непривлекательные варианты, которых я хочу избежать:

  • расширение типа данных Block таким образом, чтобы оно включало список слов, который сводится к созданию нового расширенного типа данных Pandoc с большим количеством (хрупкого) кода котельной пластины

  • отображение блоков в списки слов; что является неоптимальным, так как блоки слишком сложны, чтобы эффективно служить ключами

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

Post scriptum 2011-06-12 :

Как показывают комментарии, я, вероятно, переоценил стоимость подхода, основанного на карте, частично основываясь на неправильных предположениях. На самом деле: «нет ничего более обманчивого, чем очевидный факт».

В любом случае, я принимаю ответ hammar, потому что он иллюстрирует, как создать расширяемый тип данных.

Спасибо

1 Ответ

4 голосов
/ 11 июня 2011

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

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

data Tree = Leaf | Fork String Tree Tree

Мы можем добавить параметр для рекурсивного использования Tree: 

data GenTree t = Leaf | Fork String t t

Теперь, чтобы получить простое дерево, подобное оригиналу, мы берем фиксированную точку этого типа: 

data Fix a = Fix (a (Fix a))
type Tree = Fix GenTree

Теперь вы можете расширить тип дополнительными данными на каждом рекурсивном сайте. Вот как сделать тип для помеченных деревьев: 

data Labelled t = Labelled Int (GenTree t)
type LabelledTree = Fix Labelled

strLength :: GenTree t -> Int
strLength Leaf = 0
strLength (Fork str _ _) = length str

label :: Tree -> LabelledTree
label (Fix tree) = Fix $ Labelled (strLength tree) (fmap label tree)

instance Functor GenTree where
    fmap f Leaf = Leaf
    fmap f (Fork s l r) = Fork s (f l) (f r)
...