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

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

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

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

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


haskell monads applicative
person MathematicalOrchid    schedule 27.02.2013    source источник

Ответы (3)


arrow_upward
11
arrow_downward 

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

Or

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

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

person dave4420    schedule 27.02.2013
comment
Мы хотим игнорировать значение (но не эффект) many1 space и применить read к значению many1 digit. (Извините, я только что вошел, уже поздно, я устал: я играю быстро и свободно с терминологией.) Если вы представляете, что s и d представляют значения many1 space и many1 digit соответственно, то значение (игнорируя эффекты) из const read <$> many1 space <*> many1 digit равно const read s d = read d. - person dave4420; 01.03.2013

arrow_upward
39
arrow_downward

я бы написал

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

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

person pigworker    schedule 27.02.2013
comment
Вау, я знал о <$, но я когда-либо использовал его только в том случае, если слева от него была константа, а справа — простое значение... Я никогда не думал о том, что произойдет, если я поставлю функцию слева: П Хороший трюк - person Niklas B.; 28.02.2013

arrow_upward
8
arrow_downward

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

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. 3-й монадный закон (ассоциативность):

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

  5. определение liftM (в нотации, отличной от do):

    liftM read (many1 space >> many1 digit)

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

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

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

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

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

person Matt Fenwick    schedule 01.03.2013
comment
Прохладный! Другой способ написать read <$ many1 space <*> many1 digit. :) Последнее предложение очень важно. Означает ли это, что этот стиль соответствует контекстно-свободным грамматикам, а более общие грамматики должны анализироваться монадическим стилем? - person Will Ness; 05.03.2013
comment
@WillNess Я не эксперт в этом, но я верю, что это так. - person Matt Fenwick; 05.03.2013