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

StackOverflow https://stackoverflow.com/questions/6316090

  •  26-10-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

Постскриптум 12 июня 2011 г.:

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

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

Спасибо

Это было полезно?

Решение

Вы не можете добавлять что-либо к существующему типу данных, если он не предназначен для расширения, поэтому вам придется полагаться на некоторую внешнюю структуру, например 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)
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top