Недавно я прочитал Вкус карри и впоследствии решил проверить пример тривиального арифметического парсера, написав несколько более существенный парсер: примитивный, но правильный и функциональный HTML-парсер.
В итоге я получил работающую функцию node2string
для работы с Node
(с атрибутами и дочерними элементами), которую я затем inverse
d получил для получения функции parse
, как показано в статье.
В первой наивной реализации была ошибка, заключавшаяся в том, что она анализировала что угодно, кроме, например, тривиальный <input/>
HTML-фрагмент ровно в одно Node
представление; все остальное недетерминировано дало недопустимые вещи, такие как
Node { name = "input", attrs = [Attr "type" "submit"] }
Node { name = "input type=\"submit\"", attrs = [] }
и так далее.
После некоторых первоначальных наивных попыток исправить это изнутри node2string
, я осознал момент, который, я думаю, мгновенно увидят все опытные логические программисты, что parse = inverse node2string
был прав более прав и проницателен в отношении ситуации, чем я: приведенные выше 2 результата синтаксического анализа <input type="submit"/>
действительно были ровно 2 действительными и конструируемыми значениями Node
, которые привели бы к представлениям HTML.
Я понял, что должен ограничить Node
, чтобы разрешить передачу только в алфавитном порядке - ну, не совсем, но давайте будем проще - имена (и, конечно, то же самое для Attr
). В менее фундаментальной настройке, чем логическая программа (например, обычный Haskell с гораздо большим количеством написанного от руки и «учебного» в отличие от чисто декларативного программирования), я бы просто скрыл конструктор Node
, например, за mkNode
дозорная функция, но у меня есть ощущение, что это не будет хорошо работать в Curry из-за того, как работает механизм вывода или решатель ограничений (я могу ошибаться в этом, и на самом деле я надеюсь, что это так).
Поэтому вместо этого я получил следующее. Я думаю, что метапрограммирование Curry (или Template Haskell, если бы Curry его поддерживал) можно было бы использовать для очистки ручного шаблона, но косметический подход — это только один из выходов из ситуации.
data Name = Name [NameChar] -- newtype crashes the compiler
data NameChar = A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
name2char :: NameChar -> Char
name2char c = case c of A -> 'a'; B -> 'b'; C -> 'c'; D -> 'd'; E -> 'e'; F -> 'f'; G -> 'g'; H -> 'h'; I -> 'i'; J -> 'j'; K -> 'k'; L -> 'l'; M -> 'm'; N -> 'n'; O -> 'o'; P -> 'p'; Q -> 'q'; R -> 'r'; S -> 's'; T -> 't'; U -> 'u'; V -> 'v'; W -> 'w'; X -> 'x'; Y -> 'y'; Z -> 'z'
name2string :: Name -> String
name2string (Name s) = map name2char s
-- for "string literal" support
nameFromString :: String -> Name
nameFromString = inverse name2string
data Node = Node { nodeName :: Name, attrs :: [Attr], children :: [Node] }
data Attr = Attr { attrName :: Name, value :: String }
attr2string :: Attr -> String
attr2string (Attr name value) = name2string name ++ "=\"" ++ escape value ++ "\""
where escape = concatMap (\c -> if c == '"' then "\\\"" else [c])
node2string :: Node -> String
node2string (Node name attrs children) | null children = "<" ++ name' ++ attrs' ++ "/>"
| otherwise = "<" ++ name' ++ attrs' ++ ">" ++ children' ++ "</" ++ name' ++ ">"
where name' = name2string name
attrs' = (concatMap ((" " ++) . attr2string) attrs)
children' = intercalate "" $ map (node2string) children
inverse :: (a -> b) -> (b -> a)
inverse f y | f x =:= y = x where x free
parse :: String -> Node
parse = inverse node2string
Это, на самом деле, работает отлично (на мой взгляд):
Parser> parse "<input type=\"submit\"/>"
(Node [I,N,P,U,T] [(Attr [T,Y,P,E] "submit")] [])
Parser> parse "<input type=\"submit\" name=\"btn1\"/>"
(Node [I,N,P,U,T] [(Attr [T,Y,P,E] "submit"),(Attr [N,A,M,E] "btn1")] [])
(У Curry нет классов типов, поэтому я пока не знаю, как заставить [NameChar]
печатать более красиво)
Тем не менее, мой вопрос:
есть ли способ использовать что-то вроде isAlpha
(или, конечно, функцию, более соответствующую фактической спецификации HTML) для достижения результата, эквивалентного этому, без необходимости проходить подробный шаблон, которым является NameChar
и его «вспомогательные члены»? Кажется, нет никакого способа даже поместить «функциональное ограничение» где-нибудь в АТД.
В языке программирования функциональной логики с зависимой типизацией я бы просто выразил ограничение на уровне типа и позволил механизму вывода или решателю ограничений справиться с ним, но здесь я, кажется, в растерянности.