Хабрахабр

[Перевод] Аппликативные регулярные выражения, как свободный альтернативный функтор

В своём блоге in Code этот автор достаточно легким языком рассказывает о математической сути красивых и изящных функциональных решений для практических задач. Предлагаю вашему вниманию перевод замечательной свежей статьи Джастина Ле. В этой статье подробно разбирается пример того, как перенос математической структуры, которую образуют данные в предметной области на систему типов программы, может сразу, как писали Джеральд и Сассман "автомагически", привести к работающему решению.

Высший класс, настоящая магия типов! Приведённый на картинке код — это полноценная самодостаточная, расширяемая реализация парсера регулярных выражений, написанная "с нуля".

Свободные структуры — одни из моих любимых инструментов в Haskell и я уже писал ранее о свободных группах, вариациях на тему свободных монад и о "свободном" аппликативном функторе на моноидах. Сегодня мы реализуем аппликативные регулярные выражения и парсеры (в духе библиотеки regex-applicative), используя свободные алгебраические структуры!

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

Если его запустить (./regexp.hs), будет запущена сессия GHCi со всеми определениями, так что у вас будет возможность поиграть с функциями и их типами. Весь код, приведённый в статье, доступен онлайн в виде “stack executable”.

Он требует знания основных понятий языка: сопоставления с образцом, алгебраических типов данных и абстракций вроде моноидов, функторов и do-нотации. Эта статья будет вполне понятна "продвинутому новичку", либо "начинающему специалисту" в Haskell.

Формально такое выражение строится из трёх базовых элементов: Регулярное выражение — это способ определения некоторого регулярного языка.

  1. Пустое множество — элемент, который не сопоставляется ни с чем.
  2. Пустая строка — нейтральный элемент, который тривиально сопоставляется с пустой строкой.
  3. Литерал — символ, сопоставляемый с самим собой. Множество из одного элемента.

А также из трёх операций:

  1. Конкатенация: RS, последовательность выражений. Произведение множеств (декартово).
  2. Альтернатива: R|S, выбор между выражениями. Объединение множеств.
  3. Звезда Клини: R*, повторение выражения произвольное число раз (включая ноль).

Из этих основных компонентов можно сконструировать все прочие известные операции над регулярными выражениями — например, a+ можно выразить как aa*, а категории вроде \w можно представить в виде альтернативы подходящих символов. И это всё что составляет регулярные выражения, ни больше, ни меньше.

Примечание переводчика

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

Мне она очень напоминает класс типов Alternative. При взгляде на структуру регулярных выражений не кажется ли она чем-то знакомым? Если функтор принадлежит этому классу, то это значит, что для него определены:

  1. Пустой элемент empty, соответствующий неудаче, или ошибке в вычислениях.
  2. pure x — единичный элемент (из класса Applicative).
  3. Операция <*>, организующая последовательные вычисления.
  4. Операция <|>, организующая альтернативные вычисления.
  5. Функция many — операция повторения вычислений ноль или более раз.

Пожалуй, альтернативный функтор почти то, что нам нужно, единственное чего не хватает, это примитива, соответствующего символу-литералу. Всё это очень похоже на конструкцию регулярного языка, не так ли?

Но в рамках нашей статьи, этот класс представляет просто "двойной моноид" с двумя способами комбинирования <*> и <|>, которые, в некотором смысле, можно сопоставить с операциями * и + для чисел. Тот кто не знаком с классом Alternative, сможет найти хорошее введение в Typeclassopedia. В общем, для определения альтернативного функтора достаточно перечисленных пяти пунктов и некоторых дополнительных законов коммутативности и дистрибутивности.

Примечание переводчика (зануды)

Класс Alternative расширяет аппликативный функтор, являющийся (при определённых ограничениях) полугруппой, до полукольца, где роль коммутативного моноида играет операция сложения <|> с нейтральным элементом empty. Если быть точным, автор несколько погорячился с "двойным моноидом". Оператор аппликации

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Однако, наряду с оператором <*>, в пакете Control. не может выступать в качестве аналога операции умножения в полукольце, поскольку он не образует даже магму. Каждый из них игнорирует результат работы того операнда, на который не показывает "уголок": Applicative определены "однобокие" операторы *> и <*.

(<*) :: Applicative f => f a -> f b -> f a
(*>) :: Applicative f => f a -> f b -> f b

Можно проверить, что для альтернативного функтора умножение дистрибутивно относительно сложения, как справа, так и слева и, кроме того, нейтральный элемент для сложения (аналог нуля) является поглощающим элементом для операции умножения. Если, типы a и b совпадают, то с этими операциями мы получаем полугруппу (ассоциативность вытекает из свойств композиции).

Полукольца также образуют числа, множества, матрицы полуколец, алгебраические типы и… регулярные выражения, так что, действительно мы говорим об одной и той же алгебраической структуре.

Но, есть и другой способ взглянуть на них, и он ведёт нас прямо к свободным структурам. Таким образом, мы можем рассматривать регулярные выражения как альтернативный функтор, плюс примитив для символа-литерала. Вместо "альтернативного функтора с литералами", мы можем превратить литерал в экземпляра класса Alternative.

Тип для примитива-литерала: Давайте так и напишем.

data Prim a = Prim Char a deriving Functor

Это связано с тем, что, определяя экземпляр для классов Functor, Applicative и Alternative мы должны иметь тип-параметр. Заметим, что поскольку мы работаем с функторами (аппликативными, альтернативными), то со всеми нашими регулярными выражениями будет ассоциирован некий "результат".

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

В нашем случае Prim 'a' 1 :: Prim Int будет представлять примитив, который сопоставляется с символом 'a', и сразу же интерпретируется, давая в результате единицу.

Ну, а теперь… придадим нашему примитиву нужную математическую структуру, используя свободный альтернативный функтор из библиотеки free:

import Control.Alternative.Free type RegExp = Alt Prim

Это и есть наш полноценный тип для регулярных выражений! Вот и всё! Теперь мы имеем: Объявив тип Alt экземпляром класса Functor, мы получили все операции из классов Applicative и Alternative, поскольку в этом случае существуют экземпляры Applicative (Alt f) и Alternative (Alt f).

  • Тривиальное пустое множество — empty из класса Alternative
  • Пустую строку — pure из класса Applicative
  • Символ-литерал — базовый функтор Prim
  • Конкатенацию — <*> из класса Applicative
  • Альтернативу — <|> из класса Alternative
  • Звезду Клини — many из класса Alternative

И всё это мы получили совершенно "бесплатно", то есть, "for free"!

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

После добавления некоторых удобных функций-обёрток… работа над типом завершена!

-- | charAs: Интерпретирует указанный символ, как некоторую константу
charAs :: Char -> a -> RegExp a
charAs c x = liftAlt (Prim c x) -- liftAlt :: f a -> Alt f a позволяет использовать -- базовый функтор Prim в типе RegExp -- | char: Интерпретирует и возвращает в качестве результата указанный символ
char :: Char -> RegExp Char
char c = charAs c c -- | string: Интерпретирует и возвращает в качестве результата указанную строку
string :: String -> RegExp String
string = traverse char -- классно, а?

Давайте сконструируем выражение (a|b)(cd)*e, возвращающее, в случае успешного сопоставления единичный тип (): Ну, что, попробуем?

testRegExp_ :: RegExp ()
testRegExp_ = void $ (char 'a' <|> char 'b') *> many (string "cd") *> char 'e'

Functor отбрасывает результат, мы используем её, поскольку нас здесь интересует лишь успех сопоставления. Функция void :: Functor f => f a -> f () из пакета Data. Но операторы <|> and *> and many используются нами именно так как предполагается при конкатенации или выборе одного из вариантов.

Вот интересный пример посложнее, давайте определим то же регулярное выражение, но теперь, в качестве результата сопоставления, посчитаем число повторений подстроки cd.

testRegExp :: RegExp Int
testRegExp = (char 'a' <|> char 'b') *> (length <$> many (string "cd")) <* char 'e'

А поскольку many (string "cd") :: RegExp [String] возвращает список повторяющихся элементов мы можем, оставаясь внутри функтора, вычислить длину этого списка, получив число повторений. Тут есть тонкость в работе операторов *> and <*: стрелочки показывают на тот результат, который следует сохранить.

Более того, расширение компилятора GHC -XApplicativeDo позволяет записать наше выражение с использование do-нотации, которая, возможно, легче для понимания:

testRegExpDo :: RegExp Int
testRegExpDo = do char 'a' <|> char 'b' cds <- many (string "cd") char 'e' pure (length cds)

Вот пример на Ruby: Это всё в чём-то похоже на то как мы "захватываем" результат разбора строки с помощью регулярного выражения, получая доступ к нему.

irb> /(a|b)((cd)*)e/.match("acdcdcdcde")[2]
=> "cdcdcdcd"

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

Вот ещё одна удобная регулярка \d, соответствующая цифре от 0 до 9 и возвращающая число:

digit :: RegExp Int
digit = asum [ charAs (intToDigit i) i | i <- [0..9] ]

Applicative. Здесь функция asum из пакета Control. Char. Alternative представляет выбор из элементов списка asum [x,y,z] = x <|> y <|> z, а функция intToDigit определена в пакете Data. И, опять же, мы можем создавать достаточно изящные вещи, например, выражение \[\d\], соответствующее цифре в квадратных скобках:

bracketDigit :: RegExp Int
bracketDigit = char '[' *> digit <* char ']'

Отлично! Ну, хорошо, всё, что мы сделали, это описали тип данных для литерала с конкатенацией, выбором и повторениями. Как нам в этом поможет свободный альтернативный функтор? Но что нам по-настоящему нужно так это сопоставление строки с регулярным выражением, верно? Давайте рассмотрим два способа сделать это! На самом деле, существенно поможет.

Разгружаем альтернативный функтор

Что такое "свобода"?

Например, преобразование foldMap превращает свободный моноид (список) в значение любого экземпляра класса Monoid: Канонический способ использования свободной структуры состоит в её свёртке в конкретную структуру с помощью подходящей алгебры.

foldMap :: Monoid m => (a -> m) -> ([a] -> m)

Общая идея состоит в том, что использование свободной структуры позволяет отложить её конкретное использование "на потом", разделяя время создания и время использования структуры. Функция foldMap превращает преобразование a -> m в преобразование [a] -> m (или, FreeMonoid a -> m), с конкретным моноидом m.

Например, мы можем сконструировать свободный моноид из чисел:

-- | Превращает "примитив" `Int` в свободноый моноид над `Int`, аналогично `liftAlt`.
liftFM :: Int -> [Int]
liftFM x = [x] myMon :: [Int]
myMon = liftFM 1 <> liftFM 2 <> liftFM 3 <> liftFM 4

А теперь мы можем решить, как мы хотим интерпретировать операцию <>:
Может быть, это сложение?

ghci> foldMap Sum myMon
Sum 10 -- 1 + 2 + 3 + 4

Или умножение?

ghci> foldMap Product myMon
Product 24 -- 1 * 2 * 3 * 4

А может быть, вычисление максимального числа?

ghci> foldMap Max myMon
Max 4 -- 1 `max` 2 `max` 3 `max` 4

Свободный моноид над числами определяет такую структуру над ними, какую нужно, ни больше, ни меньше. Идея состоит в том, чтоб отложить выбор конкретного моноида, сперва соорудив свободную коллекцию чисел 1, 2, 3, и 4. Для использования foldMap мы указываем "как воспринимать базовый тип", передавая оператор <> конкретному моноиду.

Интерпретация в функторе State

В нашем случае, нам повезло, существует конкретная реализация класса Alternative, которая работает ровно так, как нам необходимо: StateT String Maybe. На практике, получение результата из свободной структуры состоит в отыскании (или создании) подходящего функтора, который обеспечит нам нужное поведение.

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

Она сохраняет состояние со времени последнего удачного выполнения разбора и возвращается к нему при неудачном выборе альтернативы. А его сумма <|> работает как бэктрекинг, поиск с возвратом к альтернативе в случае неудачи. Это именно то поведение, что мы ожидаем от выражения R|S.

Наконец, натуральное преобразование для свободного альтернативного функтора называется runAlt:

runAlt :: Alternative f => (forall b. p b -> f b) -> Alt p a -> f a

Или, для типа RegExp:

runAlt :: Alternative f => (forall b. Prim b -> f b) -> RegExp a -> f a

Смысл тут в том, что нужно предоставить runAlt функцию, работающую с Prim b для абсолютно любого b, а не какого-то конкретного типа, как Int и Bool, например. Если вы не знакомы с RankN-типами (с конструкцией forall b.), то можете посмотреть хорошее введение здесь. В нашем случае, ответить на вопрос: "Что нужно сделать с типом Prim?" То есть, как и при работе с foldMap мы должны лишь указать, что делать с базовым типом.

processPrim :: Prim a -> StateT String Maybe a
processPrim (Prim c x) = do d:ds <- get guard (c == d) put ds pure x

Напомню, что Prim содержит информацию о сопоставляемом символе c и о его интерпретации в виде некоторого значения x. Это интерпретация Prim как действия в контексте StateT String Maybe, где состоянием является не разобранная ещё строка. Обработка Prim состоит из следующих шагов:

  • Получаем с помощью get состояние (не разобранную ещё часть строки) и тут же выдяем её первый символ и остаток. Если строка пуста, произойдёт возврат с альтернативному варианту. (Трансформер StateT действует внутри функтора Maybe и при невозможности сопоставления с образцом в правой части оператора <- внутри блока do, вычисления завершатся с результатом empty, то есть, Nothing. прим. пер.).
  • Используем охраняющее выражение guard для сопоставления текущего символа с заданным. В случае неудачи, возвращается empty, и мы переходим к альтернативному варианту.
  • Изменяем состояние, заменяя разбираемую строку на её "хвост", поскольку к этому моменту текущий символ уже можно считать успешно разобранным .
  • Возвращаем то, что должен возвращать примитив Prim.

Для этого нужно запустить вычисления с помощью runAlt и runStateT, передав последней функции разбираемую строку в качестве аргумента: Эту функцию уже можно использовать для сопоставления RegEx с префиксом строки.

matchPrefix :: RegExp a -> String -> Maybe a
matchPrefix re = evalStateT (runAlt processPrim re)

Посмотрим как работает наше первое решение: Bот и всё!

ghci> matchPrefix testRegexp_ "acdcdcde"
Just ()
ghci> matchPrefix testRegexp_ "acdcdcdx"
Nothing
ghci> matchPrefix testRegexp "acdcdcde"
Just 3
ghci> matchPrefix testRegexp "bcdcdcdcdcdcdcde"
Just 7
ghci> matchPrefix digit "9"
Just 9
ghci> matchPrefix bracketDigit "[2]"
Just 2
ghci> matchPrefix (many bracketDigit) "[2][3][4][5]"
Just [2,3,4,5]
ghci> matchPrefix (sum <$> many bracketDigit) "[2][3][4][5]"
Just 14

Погодите, что это было?

Минуту назад мы написали наш примитив, а потом раз! Похоже, всё случилось несколько быстрее, чем вы ожидали. Вот, собственно, весь ключевой код, несколько строк на Haskell: и работающий парсер готов.

import Control.Monad.Trans.State (evalStateT, put, get)
import Control.Alternative.Free (runAlt, Alt)
import Control.Applicative
import Control.Monad (guard) data Prim a = Prim Char a deriving Functor type RegExp = Alt Prim matchPrefix :: RegExp a -> String -> Maybe a
matchPrefix re = evalStateT (runAlt processPrim re) where processPrim (Prim c x) = do d:ds <- get guard (c == d) put ds pure x

Что произошло? И у нас есть полнофункциональный парсер регулярных выражений?

Что, по существу, делает runAlt — использует поведение конкретного альтернативного функтора (в нашем случае, StateT String Maybe) для управления поведением операторов pure, empty, <*>, <|>, и many. Вспомним, что на высоком уровне абстракции, Alt Prim уже содержит в своей структуре pure, empty, Prim, <*>, <|>, и many (с этим оператором есть одна неприятная тонкость, но о ней позже). Однако, StateT не имеет встроенного оператора, аналогичного Prim, и для этого нам понадобилось написать processPrim.

Таким образом, 83% работы за нас выполняет функтор StateT, а оставшиеся 17% — processPrim. Итак, для типа Prim функция runAlt использует processPrim, а для pure, empty, <*>, <|>, и many используется подходящий экземпляр класса Alternative. Можно задаться вопросом: а зачем было вообще начинать с обёртки Alt? По-правде сказать, это несколько разочаровывает. Если всё делается в функторе StateT, то зачем заморачиваться с Alt — свободным альтернативным функтором? Почему бы сразу не определить тип RegExp = StateT String Maybe и подходящий примитив char :: Char -> StateT String Maybe Char?

А на самом деле, он мощный, до абсурда. Основное преимущество Alt перед StateT состоит в том, что StateT это… достаточно мощный инструмент. Скажем, что-то элементарное вроде put "hello" :: StateT String Maybe () не соответствует никакому корректному регулярному выражению, но при этом имеет тип идентичный RegExp (). С его помощью можно представлять огромное число самых разнообразных вычислений и структур, и, что неприятно, легко представить нечто не являющееся регулярным выражением. Тип Alt Prim — это идеальное представление регулярного выражения. Таким образом, в то время как мы говорим, что Alt Prim соответствует регулярному выражению, не больше, но и не меньше, мы не можем утверждать то же самое относительно StateT String Maybe. Здесь, впрочем, тоже есть некоторые неприятные тонкости, связанные с ленивостью Haskell, подробнее об этом позже. Всё, что может быть выражено с его помощью является регулярным выражением, но что-либо таким выражением не являющееся выразить с его помощью не выйдет.

Но можно представить себе и другие способы использования типа RegExp. Здесь мы можем рассматривать StateT лишь как контекст, используемый для одной
интерпретации регулярного выражения — в виде парсера. Например, нам может понадобиться его текстовое представление, это то, что StateT сделать не позволит.

Но про Alt Prim мы можем точно утверждать, что это и есть регулярное выражение (как говорят математики, они равны с точностью до изоморфизма, прим. Мы не можем сказать, что StateT String Maybe — это регулярное выражение, только то, что этот функтор может представить парсер, основанный на регулярных грамматиках. пер.).

Непосредственное использование свободной структуры

Есть ли возможность использовать свободную структуру Alt напрямую, чтобы написать парсер? Всё это, конечно, очень хорошо, но что если мы не хотим перекладывать 83% работы на код для типа, который был написан кем-то за нас. Как непосредственно оперировать этой структурой вместо делегирования работы какому-то конкретному моноиду? Этот вопрос подобен такому: как написать функцию, обрабатывающую списки (сопоставляя конструкторы (:) и []) вместо использования только foldMap?

Давайте взглянем на определение свободного альтернативного функтора: Рад, что вы спросили!

newtype Alt f a = Alt data AltF f a = forall r. Ap (f r) (Alt f (r -> a)) | Pure a

Один из способов его понять, представить себе, что Alt xs содержит цепочку альтернатив, формируемую с помощью оператора <|>. Это необычный тип, определённый через взаимную рекурсию, так что он может выглядеть весьма запутанно. И каждая такая альтернатива представлена типом AltF, который является последовательностью функторов f, формируемой с помощью оператора <*> (как последовательность вложенных функций).

Ap соответствует конструктору (:), содержащему f r, а Pure — концу списка []. Можно рассматривать AltF f a как односвязный список [f r], с различными r у каждого элемента. Конструкция forall r. здесь обозначает квантор существования из расширения -XExistentialQuantification и именно он позволяет соединять различные типы в цепочку.

Либо можно взглянуть на него, как на нормализованную форму последовательных (или вложенных) операций <*> и <|>, подобно тому, как тип [a] является нормализованной формой последовательных операций <>. В конце концов, Alt f подобен списку альтернатив, каждая из которых представляет цепочку аппликаций.

Примечание переводчика

Это несколько туманное место в оригинальной статье, я хочу пояснить простыми примерами:

  • Свободный моноид (список) — цепочка, образуемая оператором <>:

    [a,b,c,d] = [a]<>[b]<>[c]<>[d]

  • Свободное полукольцо (алгебра) — список слагаемых, образуемый оператором +, содержащий произведения — цепочки, образуемые оператором *:

    a*(b+c)+d*(x+y+z)*h

  • Свободный альтернативный функтор (Alt f) — список альтернатив, образуемый оператором <|>, содержащий аппликации — цепочки, образуемые оператором <*>:

    f a <*> (f b <|> f c) <|> f d <*> (f x <|> f y <|> f z) <*> f h

Это можно сделать с помощью самых базовых принципов определения функций: с помощью сопоставления с образцом и обработки всех вариантов. В конечном счёте, мы хотим написать функцию с типом RegExp a -> String -> Maybe a, которая разбирает строку, в соответствии с регулярным выражением.

Имея список цепочек, мы можем разбирать их все по очереди до первого удачного сопоставления, которое и станет результатом разбора. Для начала, обработаем тип Alt.

matchAlts :: RegExp a -> String -> Maybe a
matchAlts (Alt res) xs = asum [ matchChain re xs | re <- res ]

(Эта функция используется здесь, поскольку тип Maybe a является каноническим и простейшим экземпляром класса Alternative — нулём является Nothing, а оператор <|> возвращает первый ненулевой операнд. Здесь функция asum :: [Maybe a] -> Maybe a находит первый элемент, завёрнутый в Just. пер.) прим.

Для этого следует рассмотреть конструкторы типа AltF, то есть Ap и Pure: Теперь нужно обработать цепочки аппликаций.

matchChain :: AltF Prim a -> String -> Maybe a
matchChain (Ap (Prim c x) next) cs = _
matchChain (Pure x) cs = _

(В Haskell "дырками" (holes) называются незаполненные термы в коде, обозначаемые символом _, тип которых может быть выведен компилятором. Дальше остаётся преимущественно игра в "тетрис на типах": мы можем продолжать спрашивать GHC чем заполнить "дырки", до тех пор, пока не получим решение, проходящее проверку типов. пер.) В результате этого вполне механического процесса мы получим: прим.

matchChain :: AltF Prim a -> String -> Maybe a
matchChain (Ap (Prim c x) next) cs = case cs of [] -> Nothing d:ds | c == d -> matchAlts (($ x) <$> next) ds | otherwise -> Nothing
matchChain (Pure x) _ = Just x

Тогда в случае пустой строки разбор можно считать неудачным, а в противном случае всё становится интереснее. Если разбирается Ap (аналогичный конструктору (:)), то значит, мы где-то в середине аппликативной цепочки. Если сопоставление прошло удачно, мы продолжаем вычисления передавая их выражению next. У нас есть Prim r, содержащий сопоставляемый символ, первый символ в строке и следующее регулярное выражение в цепочке next :: RegExp (r -> a). Наконец, если разбираемое выражение является Pure x (аналогичное пустому списку []), значит, цепочка окончена, и мы готовы передать успешный результат. В противном случае, "сообщаем" о неудаче, возвращая Nothing.

Конечно же, полезно понимать, что "в действительности" означают все эти Ap, Pure, AltF и т.д., но можно положиться на систему типов и позволить ей самой найти решение. Впрочем, нет необходимости столь глубоко вникать во все детали, чтобы написать такую программу.

Этого вполне достаточно для реализации ещё одного анализатора префикса строки:

ghci> matchAlts testRegexp_ "acdcdcde"
Just ()
ghci> matchAlts testRegexp_ "acdcdcdx"
Nothing
ghci> matchAlts testRegexp "acdcdcde"
Just 3
ghci> matchAlts testRegexp "bcdcdcdcdcdcdcde"
Just 7
ghci> matchAlts digit "9"
Just 9
ghci> matchAlts bracketDigit "[2]"
Just 2
ghci> matchAlts (many bracketDigit) "[2][3][4][5]"
Just [2,3,4,5]
ghci> matchAlts (sum <$> many bracketDigit) "[2][3][4][5]"
Just 14

Примечание переводчика

Например, если мы захотим ввести дополнение (отрицание) выражения, то возникнет необходимость зайти внутрь свободной структуры и преобразовать её должным образом. Понимание и детальный разбор свободной структуры могут быть очень полезны для расширения нашего типа. И это можно сделать, подобно тому, как показано выше.

Поскольку списки ведут себя, как свободный моноид, любая функция над списками может быть записана через foldMap, и если это кажется невероятным, то попробуйте отыскать такую функцию, для которой это невозможно, и вы удивитесь! Рассмотренные нами два подхода к интерпретации свободной структуры можно сравнить с обработкой списка через преобразование foldMap или через сопоставление с образцом. Однако, поскольку список — это алгебраический тип данных, любая функция также может быть записана непосредственно через его деструкцию — сопоставление с конструкторами (:) и [].

Мы говорим, что свободный моноид нормализует структуру. У списка, как свободного моноида, есть одно хорошее свойство: неважно, как он строится, в результате получится последовательность, соединённая (:), завершающаяся []. Так что, при разборе алгебраического типа, мы не различим этих два списка. Это значит, что [1,2,3] <> [4] будет иметь то же самое представление, что и [1] <> [2,3] <> [4].

Приведём вариант, который не обладает таким свойством: Свободный альтернативный функтор так же нормализует свою структуру.

data RegExp a = Empty | Pure a | Prim Char a | forall r. Seq (RegExp r) (RegExp (r -> a)) | Union (RegExp a) (RegExp a) | Many (RegExp a)

Однако это представление не является нормализующим. Так мы могли бы определить тип RegExp, если бы не знали о свободном альтернативном функторе. Например, такие два разных экземпляра типа RegExp представляют одно и то же регулярное выражение:

-- | a|(b|c)
abc1 :: RegExp Int
abc1 = Prim 'a' 1 `Union` (Prim 'b' 2 `Union` Prim 'c' 3) -- | (a|b)|c
abc2 :: RegExp Int
abc2 = (Prim 'a' 1 `Union` Prim 'b' 2) `Union` Prim 'c' 3

Таким образом, в ненормализующей свободной структуре одно и тоже выражение можно представить несколькими различными способами.

Это значит, что когда мы писали нашу функцию matchAlts, нас не должно было волновать то как именно была собрана разбираемая структура. В этом отношении Alt Prim лучше, поскольку если два однородных регулярных выражения одинаковы, то мы можем быть вполне уверены в том, что они будут иметь одинаковые внутренние представления. Благодаря нормализующим свойствам функтора Alt мы вынуждены рассматривать эти два выражения как одинаковые. Мы не должны различать (a|b)|c и a|(b|c). Соответственно, мы вынуждены подчиняться и законам, справедливым для регулярных выражений.

Использование Alt вместо такого представления не только упрощает разработку, но и исключает большой пласт потенциальных ошибок. Нетрудно представить себе ошибку, которая могла бы возникнуть, если бы мы случайно обрабатывали выражение (a|b)|c не так, как (a|b)|c, что, действительно, легко сделать используя ненормализующее представление типа RegExp.

Например, Alt Prim будет различным образом представлять идентичные выражения a|a и a. Однако, следует заметить, что хотя функтор Alt и нормализует однородные структуры, Alt Prim не является нормализующим во всех возможных случаях. Но как и во многих случаях структурной типобезопасности, я придерживаюсь правила: слишком много безопасности лучше её отсутствия. Это связано с тем, что функтор Alt f не использует никакой информации о функторе f. Эта методика не может избавить от всех ошибок, но, всё же, огромное их число будет исключено.

Вы можете спокойно пропустить этот раздел, если вас не волнует то обстоятельство, что построенный нами математический формализм не является в точности идентичным регулярным выражениям. Прежде чем перейти к заключению, следует прояснить один тонкий момент. И хотя мы можем использовать наш тип RegExp на практике, формальная концепция регулярных выражения немного от него отличается в силу одной важной, но надоедливой вещи — ленивости.

Например, именно из-за ленивости [a] не является истинным математическим свободным моноидом. Это не должно удивлять, поскольку ленивость языка вмешивается во многие математические абстракции в Haskell. прим. (Здесь имеется в виду возможность сконструировать бесконечный список, при попытке осуществить его преобразование в какой-либо другой моноид, мы получим "пустой" тип $\bot$, который не может быть частью какой-либо "нормальной" структуры. пер.)

прим. Ленивость языка позволяет нам создать бесконечное выражение: a|aa|aaa|aaaa|aaaaa|aaaaaa|..., в то время как бесконечные регулярные выражения не допускаются в строгой математической версии (вспомним, что согласно классификации Хомского, регулярный язык может быть обработан конечным автоматом, что невозможно для приведённой бесконечной грамматики. К сожалению, в Haskell мы не можем выключить рекурсию. пер.). То есть, a* реализуется как a|aa|aaa|aaaa|aaaaa|aaaaaa|..., и во время парсинга мы полагаемся на ленивость языка и бесконечность списка альтернатив. Что ещё печальнее, именно таким образом Alt реализует оператор many. Haskell без рекурсии вполне годится при использовании Alt для беззвёздочного языка, но это уже не регулярный язык. Если вы попытаетесь получить какое-либо текстовое представление выражения many (char 'a'), то получите бесконечный список.

Конечный автомат удастся построить лишь для конечных выражений, так что любое использование many при этом становится недопустимым. Для задач, приводимых в этой статье, это не важно, но это приведёт к серьёзным проблемам, если мы захотим построить по нашему выражению недетерминированный конечный автомат (НКА), являющийся наиболее эффективной и стандартной реализацией парсера регулярных выражений.

Мы можем использовать "конечный" вариант функтора Alt, определённый в пакете Control. Впрочем, не всё потеряно! Free. Alternative. Final, чтобы получить нерекурсивный оператор many (правда, этот вариант не сработает, до тех пока не будет реализован мой пулл реквест).

Впрочем, мы можем переключиться на такие экземпляры класса Alternative, которые не имеют рекурсивного many (как функтор RE из библиотеки regex-applicative) и позволят строить парсеры на конечных автоматах. Использование конечного функтора приведёт к потере возможности непосредственного разбора свободной структуры, оставляя нам лишь метод, использующий runAlt. Это тоже не исключает всех проблем, поскольку Haskell позволяет построить общую рекурсию где угодно, но, по крайней мере, many уже не будет зависеть от бесконечных структур.

Хотя наша рекурсивная реализация не позволяет сконструировать явный НКА (полный граф с о всеми узлами и переходами), она всё же оставляет нам возможность построить неявный автомат (автомат, имеющий в качестве одного из узлов самого себя, прим. Ещё одно интересное замечание, касающееся построния НКА. Наша реализация парсера matchPrefix, на самом деле и представляет собой неявный НКА, существующий в рантайме, где состояния автомата представляются функциональными указателями в памяти. пер.). Это позволяет обойти проблему бесконечных структур, поскольку в GHC рекурсия реализована с помощью циклов в структуре указателей. Эти указатели, в свою очередь, ссылаются на другие указатели, и общее поведение соответствует неоптимизированному НКА, который строится прямо по ходу выполнения разбора.

Также стоит написать функцию, возвращающую первый успешный результат сопоставления, с помощью гомоморфизма listToMaybe. Давайте в качестве вишенки на торте напишем последнюю функцию, отыскивающую все соответствия регулярному выражению в строке, используя функции tails (порождающую все префиксы строки) и mapMaybe (которая применяет опциональную функцию к списку аргументов и сохраняет лишь успешные результаты).

matches :: RegExp a -> String -> [a]
matches re = mapMaybe (matchPrefix re) . tails firstMatch :: RegExp a -> String -> Maybe a
firstMatch re = listToMaybe . matches re

прим. Эти решения достаточно эффективны, в силу того, что парсер matchPrefix незамедлительно возвращает Nothing при первом же несовпадении в разборе, а listToMaybe завершает работу получив первое же значение, отличное от Nothing (и здесь мы вовсю используем ленивость языка, так что нет худа без добра. пер.).

Получив набор базовых примитивов, они предоставляют вам в точности ту структуру, в которой вы нуждаетесь — не больше, но и не меньше. Надеюсь, теперь вы по достоинству оценили ценность свободных структур. Они обладают свойством нормализации, исключая тем самым бессмысленные различия, и избавляя от ошибок, связанных с разной обработкой идентичных объектов. Они позволяют безопасно работать с вашим типом, а потом обрабатывать его в том или ином контексте.

Переход от свойств регулярных выражений к функтору Alt Prim состоял в распознавании сходной математической структуры этих двух объектов, и в смене парадигмы: от альтернативного функтора, дополненного примитивом, к примитиву, дополненному до альтернативного функтора.

Для начала можно поиграть с кодом и примерами. Что ещё можно сделать в этом направлении? Далее можно легко пополнить арсенал примитивов:

data Prim a = Only Char a -- сопоставляется с символом | Letter a -- сопоставляется с любой буквой | Digit (Int -> a) -- сопоставляется с любой цифрой, | Wildcard (Char -> a) -- сопоставляется с любым символом, | Satisfy (Char -> Maybe a) -- сопоставляется с любым символом, -- удовлетворяющим условию

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

Это можно сделать с помощью runAlt или методом явной деструкции типа Alt. Интересно было бы создать генератор строки, или набора строк, соответствующих регулярному выражению.

Например, используя свободный аппликативный функтор, мы получим язык в котором есть только конкатенация, пустые строки и примитивы, но нет операции выбора. Другим любопытным направлением исследований могло бы быть построение на основе свободных структур различных типов языков (грамматик). (Нетривиальным примером может быть вычислитель выражений в обратной польской нотации, в том числе с объявлением и использованием переменных. Он подобен регулярным выражениям без операции | и сопоставляется только с однозначными цепочками. пер.). прим. Свободная структура, соответствующая классу ModadPlus позволит описывать и обрабатывать контекстно-зависимый язык с альтернативами, а ограничившись только свободным функтором мы получим язык, состоящий только из односимвольных слов. Если мы воспользуемся свободной монадой, получим контекстно-зависимый язык без поиска с возвратом. Мы получаем целую линейку языков, основанную на классификации свободных алгебраических структур.

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

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»