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

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

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

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

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

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

Регулярные языки

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

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

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

(<*) :: Applicative f => f a -> f b -> f a
(*>) :: Applicative f => f a -> f b -> f 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'

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

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

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

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

Более того, расширение компилятора 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] ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

newtype Alt f a = Alt { alternatives :: [AltF f a] }

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

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

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

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

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

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

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

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

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

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

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

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

Впрочем, нет необходимости столь глубоко вникать во все детали, чтобы написать такую программу. Конечно же, полезно понимать, что "в действительности" означают все эти 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

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

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

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

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

Некоторые досадные тонкости

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

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

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

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

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

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

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

Последние штрихи

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

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.

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

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