В Haskell, его просто создать тип данных для для рекурсивного дерева, как то, что мы имеем с XML документами:Как смоделировать структуру данных дерева с ограничениями на то, где могут появляться каждый вид узла?
data XML =
Text String -- Text of text node
| Elem String [XML] -- Tagname; Child nodes
и смежных складок:
-- Simple fold (Child trees don't see the surrounding context.)
foldt :: (String -> a) -> (String -> [a] -> a) -> XML -> a
foldt fT fE (Text text) = fT text
foldt fT fE (Elem tagname ts) = fE tagname (map (foldt fT fE) ts)
-- Threaded fold for streaming applications.
-- See http://okmij.org/ftp/papers/XML-parsing.ps.gz
foldts :: (a -> String -> a) -> (a -> String -> a) -> (a -> a -> String -> a) -> a -> XML -> a
foldts fT fE_begin fE_end = go
where
go seed (Text text) = fT seed text
go seed (Elem tag children) =
let seed' = fE_begin seed tag in
let seed'' = foldl go seed' children in
fE_end seed seed'' tag
Моя проблема сейчас в том, что я не знаю, как добавить некоторые дополнительные ограничения для моего типа данных дерева, чтобы моделировать HTML. В HTML каждый элемент узла может отображаться только в правильном contexts, и каждый элемент соответствует другому контексту для его дочерних элементов. Например:
- Элементы Void, такие как img, имеют пустую контекстную модель и не имеют детей.
- элементы с моделью содержимого текста, такие как title, могут иметь только текстовые узлы, как дети (не вложенные теги разрешены)
- div элементы не могут появляться в контексте фразировки и, следовательно, не могут быть потомками span элементов.
Так что мои вопросы:
Что я должен сделать, чтобы смоделировать эти ограничения в Haskell98? (Я спрашиваю об этом, потому что я думаю, что модель Haskell98 должна лучше переводить на другие языки программирования)
Я думаю, нам, возможно, придется создавать множество разных типов данных для разных контекстов, но я не знаю, как это сделать в принципиальном и ясным образом. Как я могу сделать это, не теряясь и что бы функции фолда выглядели так?
Как выглядит модель, если нам разрешено использовать современные функции GHC, такие как GADT?
У меня есть догадка GADTs может помочь подтолкнуть ограничения Into проверки типов, сохраняя функцию кратные простой, но я не так много опыта работы с ними ...
мне не нужен 100% -ное решение, поскольку это, очевидно, выходит за рамки обсуждения переполнения стека. Мне просто нужно достаточно, чтобы иметь возможность лучше понять GADT и такие вещи, как и сделать все возможное самостоятельно.
Я думаю, что шаблон умного конструктора применим .. но то, что вы действительно хотите здесь, звучит как зависимая типизация. http://www.haskell.org/haskellwiki/Smart_constructors – jozefg
@jozefg: подход интеллектуального конструктора помогает (и это то, что я использую сейчас), но я обнаружил, что он ограничивает то, как вам разрешено создавать материал, и он не воспроизводится очень хорошо с потоковым, SAX-подобным API. С другой стороны, если у меня есть полностью безопасная модель, я могу разработать надежную поточную версию вещей, основанную на соответствующей функции сгиба. – hugomg
@jozefg: Что касается зависимых типов, я не думаю, что нам нужно зайти так далеко, если предположить, что допустимые имена элементов из конечного набора. (Конечно, все может быть уродливым, но это точка упражнения) – hugomg