Перевести с монады на аппликацию

Question

ОК, поэтому я знаю, что класс класса Applicative содержит, и почему это полезно. Но я не могу полностью заткнуть мозг вокруг того, как вы будете использовать его в нетривиальном примере.

Рассмотрим, например, следующий довольно простой Parsec парсер:

integer :: Parser Integer 
integer = do 
    many1 space 
    ds <- many1 digit 
    return $ read ds 

Теперь, как чёрта вы пишете, что без использования экземпляра Monad для Parser? Многие люди утверждают, что это можно сделать и это хорошая идея, но я не могу понять, как именно.

Answer 1

integer :: Parser Integer 
integer = read <$> (many1 space *> many1 digit) 

Или

integer = const read <$> many1 space <*> many1 digit 

ли вы думаете, либо из них более читаемым до вас.

Answer 2

Я бы написать

integer :: Parser Integer 
integer = read <$ many1 space <*> many1 digit 

Там куча левого ассоциативно (например, приложения) парсер-строительные операторы <$>, <*>, <$, <*. Вещью в крайнем левом углу должна быть чистая функция, которая собирает значение результата из значений компонента. Вещь справа от каждого оператора должна быть парсером, в совокупности предоставляющим компоненты грамматики слева направо. Какой оператор использовать, зависит от двух вариантов:

the thing to the right is signal/noise 
    _________________________    
    the thing to the left is \   
          +------------------- 
        pure/| <$>  <$ 
        a parser | <*>  <* 

Таким образом, избрав read :: String -> Integer как чистая функция, которая собирается доставить семантику парсера, мы можем классифицировать ведущее место как «шум» и кучей цифр, как «сигнал», следовательно,

read <$ many1 space <*> many1 digit 
(..) (.........)  (.........) 
pure noise parser  | 
(.................)  | 
    parser    signal parser 
(.................................) 
        parser 

Вы можете объединить несколько возможностей с

p1 <|> ... <|> pn 

и выражают невозможность с

empty 

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

Answer 3

Ваш пример можно постепенно переписать в форме, которая более четко напоминает аппликативном:

do 
    many1 space 
    ds <- many1 digit 
    return $ read ds 

1. определение из do обозначения:

   many1 space >> (many1 digit >>= \ds -> return $ read ds) 
   

2. определение $:

   many1 space >> (many1 digit >>= \ds -> return (read ds)) 
   

3. определение .:

   many1 space >> (many1 digit >>= (return . read)) 
   

4. третьего монада закон (ассоциативность):

   (many1 space >> many1 digit) >>= (return . read) 
   

5. определение liftM (в бездокументарной do нотации):

   liftM read (many1 space >> many1 digit) 
   

Это (или должно быть, если я не испортил :)), идентичный поведению вашему примеру.

Теперь, если вы замените liftM с fmap с <$> и >> с *>, вы получите Прикладное:

read <$> (many1 space *> many1 digit) 

Это справедливо, потому что liftM, fmap и <$>, как правило, должны быть синонимами, а >> и *>.

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