Парсинг регулярных выражений на Haskell

[_Ivana]

Вчера решал одну тренировочную задачку с сайта Codewars - Regular expression parser Собственно, задание не сложное:

Цитата:

Your task is to implement a simple regular expression parser. We will have a parser that outputs the following AST of a regular expression:

Используется синтаксис Haskell

data RegExp = Normal Char       -- ^ A single regular character
            | Any               -- ^ Any charater
            | ZeroOrMore RegExp -- ^ Zero or more occurances of the same regexp
            | Or RegExp RegExp  -- ^ A choice between 2 regexps
            | Str [RegExp]      -- ^ A sequence of regexps.

Цитата:

As with the usual regular expressions, Any is denoted by the '.' character, ZeroOrMore is denoted by a subsequent '*' and Or is denoted by '|'. Brackets are allowed to group sequence of regular expressions into Str [RegExp].
Operator precedences from highest to lowest are: *, sequencing and |. Therefore the followings hold:

Используется синтаксис Haskell

"ab*"     -> Str [Normal 'a', ZeroOrMore (Normal 'b')]
"(ab)*"   -> ZeroOrMore (Str [Normal 'a', Normal 'b'])
"ab|a"    -> Or (Str [Normal 'a',Normal 'b']) (Normal 'a')
"a(b|a)"  -> Str [Normal 'a',Or (Normal 'b') (Normal 'a')]
"a|b*"    -> Or (Normal 'a') (ZeroOrMore (Normal 'b'))
"(a|b)*"  -> ZeroOrMore (Or (Normal 'a') (Normal 'b'))
"a"          -> Normal 'a'
"ab"         -> Str [ Normal 'a', Normal 'b']
"a.*"        -> Str [ Normal 'a', ZeroOrMore Any ]
"(a.*)|(bb)" -> Or (Str [Normal a, ZeroOrMore Any]) (Str [Normal 'b', Normal 'b'])

Цитата:

Feel free to use any parser combinator libraries available

Я написал простенькую программку в несколько строк безо всяких библиотек, она прошла тесты:

Используется синтаксис Haskell

parseRegExp :: String -> Maybe RegExp
parseRegExp s = Just $ go s [] where

    packlist [a] = a
    packlist  l  = Str $ reverse l

    spanclose s = (init l, drop (length l) s) where
        l = head.dropWhile ((/=(-1)).sum.map f).inits $ s
        f '(' = 1
        f ')' = -1
        f  _  = 0

    go []     l = packlist l
    go (c:cs) l = case c of
        '(' -> go sr $ go sl [] : l where (sl,sr) = spanclose cs
        '|' -> Or (packlist l) $ go cs []
        '*' -> go cs $ ZeroOrMore (head l) : (tail l)
        '.' -> go cs $ Any : l
        _   -> go cs $ Normal c : l

и это позволило мне посмотреть коды остальных участников. Начиная с кода автора задачи там были представлены обширные простыни со щедрым использованием монад/функторов/трансформеров да еще и со специализированными парсерными библиотеками нередко при этом (я не буду их приводить, но если попросите - скопипастю). И хотя я их детально не разбирал, но я примерно представляю себе их источники вдохновения, хотя я не разбираюсь в теории синтаксического разбора, порождающих грамматиках и прочему Хомскому и Брюне. Но тут на фоне всего этого великолепия я внезапно обнаружил код, который вызвал (и продолжает вызывать) у меня яркий эмоциональный отклик - вот он:

Используется синтаксис Haskell

instance Eq RegExp where
  _ == _ = True

parseRegExp _ = Just Any

и всё Не могли бы уважаемые участники форума просветить меня, как и на каких принципах работает это волшебство?

[aa_dav]

Лол, я далеко не хаскелист, только _пробовал_ начинать вникать, не смог осилить самый вменяемый учебник дальше места где собственно начались монады.
Но здесь, имхо, всё очень просто - типу RegExp перебивается оператор сравнения на то чтобы возвращать всегда True.
Таким образом сравнение с образцом теста всегда проходит :) И всего лишь.

[arseniiv]

_Ivana в сообщении #965726 писал(а):

Не могли бы уважаемые участники форума просветить меня, как и на каких принципах работает это волшебство?

Последнее-то? Ни на каких. Вы же ясно видите, что любой вход тут эквивалентен входу ".". Это точно весь код? Инстанс Eq RegExp тоже не пойму для чего. В общем, что-то здесь не так.

Кстати, а почему у вас parseRegExp s = Just something? Входу "(" должно бы соответствовать Nothing, а система тестирования почему-то съела. В ней всяко должен был быть тест на не-регексп, если уж они типом функции сделали String -> Maybe RegExp!

aa_dav в сообщении #965813 писал(а):

Но здесь, имхо, всё очень просто - типу RegExp перебивается оператор сравнения на то чтобы возвращать всегда True.

А, об этом не подумал. Тут только одна нестыковка — вроде, инстансы не могут перекрывать видимость друг друга, и два в одной и той же области видимости должны вызвать реакцию компилятора из-за невозможности выбора одной из них.

[aa_dav]

arseniiv в сообщении #965818 писал(а):

Тут только одна нестыковка — вроде, инстансы не могут перекрывать видимость друг друга, и два в одной и той же области видимости должны вызвать реакцию компилятора из-за невозможности выбора одной из них.

Опять таки я не прожженый хаскелист, но у RegExp в изначальной постановке задачи вообще инстанс Eq не был определен. Так что он по видимому просто и перебил дефолтное поведение ==.

[_Ivana]

Вы правы, я только что это понял Но это вызвало у меня не менее сильные эмоции чем в первый раз Просто делается заглушка чтобы все тесты на сравнение выдавали истину. А я дурак не додумался

ЗЫ там изначально стояло

Используется синтаксис Haskell

deriving (Show, Eq)

но участник предложивший это решение убрал Eq

[arseniiv]

aa_dav в сообщении #965824 писал(а):

Так что он по видимому просто и перебил дефолтное поведение ==.

Не бывает инстанса по-дефолту. Хотя есть способ определить такой «обычный» инстанс для некоторых классов, в т. ч. Eq, в месте описания типа с помощью добавления в конце него deriving (классы)/deriving класс.

_Ivana в сообщении #965825 писал(а):

но участник предложивший это решение убрал Eq

А, вот как. Теперь всё сходится. Правда, непонятно, почему это позволительно (могли бы немного на модули разбить, что ли), и почему нет тестов со входом типа "(".

[_Ivana]

Да, тесты только на валидные входные данные. Но мой парсер нетрудно доработать чтобы выдавал Nothing на невалидных строках.
Извините что не разобрался и создал тему по такому как оказалось смешному вопросу

[arseniiv]

(Оффтоп)

_Ivana в сообщении #965838 писал(а):

Извините что не разобрался и создал тему по такому как оказалось смешному вопросу

По-моему, нормальная тема.

[_Ivana]

На сайте изменились тесты, добавились невалидные входные данные, я доработал свой код с этим учетом с использованием монады Maybe, но проверки его процентов на 20 загромоздили. Мне это уже не так нравится, как мой исходный красивый и лаконичный вариант, может придумаю как написать лучше.

[arseniiv]

Тут как раз может пригодиться инстанс Monad Maybe, т. к.

Используется синтаксис Haskell

Nothing >>= f = Nothing
Just v  >>= f = f v

Это имеет смысл вычислений, которые могут выдать ошибку, и она распространится до самого конца.

-- Ср янв 21, 2015 03:00:00 --

(Кстати ещё, инстанс Monad (Either left) аналогичен, но передаётся информация типа left об ошибке. У подобного использования Either простая мнемоника: right — не только правое, но и «правильное», а информация об ошибке — это то, что «осталось» — left. В явном виде я этого не встречал, но, наверно, переизобретается мнемоника часто.)

[_Ivana]

arseniiv вы все правильно пишете, я это читал у Мирана Липовачи раз 10, но вот сейчас пытаюсь вместо моих ручных понятных ифов протащить через эту монаду и пока не удается. Но я вообще это делаю впервые, и вдобавок не понимаю теорию этой концепции.

-- 21.01.2015, 01:35 --

Сейчас мой безмонадный но рабочий вариант вот такой

Используется синтаксис Haskell

parseRegExp :: String -> Maybe RegExp
parseRegExp s  = go s nl where

    nl = Just []
    fall x = x == Nothing

    packlist []  = Nothing
    packlist [a] = Just $ a
    packlist  l  = Just $ Str $ reverse l

    spanclose s
        | null w    = Nothing
        | otherwise = Just (init l, drop (length l) s) where
            w = filter ((==(-1)).sum.map f).inits $ s
            l = head w
            f '(' = 1
            f ')' = -1
            f  _  = 0

    go _       Nothing = Nothing
    go []     (Just l) = packlist l
    go (c:cs) (Just l) = case c of

        '(' -> if fall sp || fall p then Nothing else go sr $ Just $ (fromJust p) : l where
            sp = spanclose cs
            (sl,sr) = fromJust sp
            p = go sl nl

        '|' -> if fall pl || fall p  then Nothing else Just $ Or (fromJust pl) (fromJust p) where
            pl = packlist l
            p = go cs nl

        '*' -> if null l then Nothing else go cs $ Just $ ZeroOrMore (head l) : (tail l)

        '.' -> go cs $ Just $ Any : l

        _   -> if not (isAlpha c) then Nothing else go cs $ Just $ Normal c : l

как его облагородить чтобы не мозолили глаза эти ифы в проверках пока думаю.

[arseniiv]

if fall sp || fall p then Nothing else v = (sp `mplus` p) >> v, хм?

[_Ivana]

Ваш вариант не понял, но мой тоже лучше того что было

Используется синтаксис Haskell

'(' -> spanclose cs >>= \(sl,sr) -> go sr $ go sl nl >>= Just.(:l)

-- 21.01.2015, 02:06 --

Вот как мне на текущий момент удалось облагородить

Используется синтаксис Haskell

parseRegExp :: String -> Maybe RegExp
parseRegExp s  = go s nl where

    nl = Just []

    packlist []  = Nothing
    packlist [a] = Just $ a
    packlist  l  = Just $ Str $ reverse l

    spanclose s
        | null w    = Nothing
        | otherwise = Just (init l, drop (length l) s) where
            w = filter ((==(-1)).sum.map f).inits $ s
            l = head w
            f '(' = 1
            f ')' = -1
            f  _  = 0

    go _       Nothing = Nothing
    go []     (Just l) = packlist l
    go (c:cs) (Just l) = case c of
        '(' -> spanclose cs >>= \(sl,sr) -> go sr $ go sl nl >>= Just.(:l)
        '|' -> packlist l >>= \pl -> go cs nl >>= \pr -> Just $ Or pl pr
        '*' -> if null l then Nothing else go cs $ Just $ ZeroOrMore (head l) : (tail l)
        '.' -> go cs $ Just $ BAny : l
        _   -> if not (isAlpha c) then Nothing else go cs $ Just $ Normal c : l

[arseniiv]

_Ivana в сообщении #965947 писал(а):

Ваш вариант не понял

MonadPlus. По существу, это одновременно Monad и Alternative. Применительно к Maybe сложение mplus означает выбор первого не провалившегося вычисления; соответственно, ноль mzero — Nothing.

-- Ср янв 21, 2015 04:14:32 --

(Или я там с типами напортачил? Мало ли, не проверял.)

[_Ivana]

MonadPlus буду кусать после Monad. Сейчас хочу запаковать

f l == True = Nothing

чтобы остальные строки нижней функции без ифов написать.