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

[nlinker]

Ещё отличный пример: библиотека optparse-applicative, весьма удобна в использовании (пример из документации):

data Sample = Sample
  { hello      :: String
  , quiet      :: Bool
  , enthusiasm :: Int }

sample :: Parser Sample
sample = Sample
      <$> strOption
          ( long "hello"
         <> metavar "TARGET"
         <> help "Target for the greeting" )
      <*> switch
          ( long "quiet"
         <> short 'q'
         <> help "Whether to be quiet" )
      <*> option auto
          ( long "enthusiasm"
         <> help "How enthusiastically to greet"
         <> showDefault
         <> value 1
         <> metavar "INT" )

[samsergey]

Да, пример, что надо! Ничего не знаю об этой библиотеке, но код смог прочесть сразу. Отличное сочетание моноидов и аппликациий! В этой связи люблю вспоминать моноидально-аппликативный fizzbuzz:

fizzbuzz = max <$> "fizz" `when` (`divisibleBy` 3)
                <> "buzz" `when` (`divisibleBy` 5)
                <> "quux" `when` (`divisibleBy` 7)
               <*> show
  where
    when x p y = if p y then x else mempty
    divisibleBy x n = x `mod` n == 0

[Livid]

В целом неплохая статья. Не совсем конечно понятно почему автор ограничился регулярными выражениями. Вообще Applicative с Alternative могут по-видимому разбирать любые контекстно-свободные языки, не только регулярные. По крайней мере автоматы с магазинной памятью в этих терминах моделируются. Как минимум рекурсивный LL(k) крайне прямолинейно записывается в терминах Applicative.

[samsergey]

Думаю, для простоты примера. Регулярки, действительно знакомы всем, а контекстно-свободные грамматики, тем кто уже хоть немного знаком с теорией языков. К тому же, кроме злополучного many, в определениях примеров выражений не используется рекурсия материнского языка (Haskell), а именно она позволяет расширить регулярную грамматику до КС. Возможно, автор хотел показать, что хоть мы и создали EDSL, наследующий полноту по Тьюрингу от вмещающего языка, он сам по себе уже обладает вычислительной мощностью НКА. Впрочем, это уже мои домыслы :) но меня привлекла именно минимальность исходных посылок: создали элементарный тип, ввели его в свободную структуру и рраз! имеем конструктор, потом определили аглебру и рраз! готов простой исполнитель.

[Livid]

Как-то я наверное не шибко хорошо сформулировал мысль.

StateT String Maybe + языковая рекурсия — это у нас уже как бы такая модель автомата с магазинной памятью (на самом деле немного не совсем, но достаточно близко). В роли "магазинной памяти" — стек вызовов.

Так что вычислительная мощность тут совсем не конечного автомата получается. И собственно если осознать, что у нас не НКА, а АМП, то "злополучный" many проблемой вроде бы и не является. Более того, АМП при анализе "сверху вниз" так и будет конструкцию подобную этому many анализировать — через "рекурсию" на стеке, пока не упрётся (либо в размер стека — который конечно в абстрактной модели бесконечный, но мы-то знаем — либо в завершение рекурсии)

Плюс в начале рассуждение о регулярных языках (тип 3 по Хомскому), в конце упоминаются КЗ-языки (тип 1). А про КС-языки (тип 2) как-то неожиданно ни слова. Причём описать КС-языки можно не сильно длиннее, чем регулярные. Дать определение КС-грамматики через БНФ, да пример показать. Разве что расчёт действительно на массовость. Что регулярные выражения все хотя бы видели, а про БНФ не все даже знают, что такое есть в природе (что конечно само по себе печально).

В общем это я всё к тому, что КС-языки тут так и просятся вместо регулярных, на мой вкус.