Функтор для парсера - PullRequest
Новая
       1

Функтор для парсера

0 голосов
/ 14 февраля 2020

В рамках домашнего задания мы работаем над анализатором в Haskell. У нас есть этот тип данных 

newtype Parser a = Parser { parse :: String -> Maybe (a,String) }

Это ясно для меня, наш анализатор получает строку, возвращаемое выражение из типа a и оставшуюся непарсированную строку.

Но затем у нас есть определение функтора: 

  instance Functor Parser where
       fmap f p = Parser $ \s -> (\(a,c) -> (f a, c)) <$> parse p s

И я полностью потерян. Мне кажется, что parse ps дает проанализированное выражение типа a, но я не могу понять, что на самом деле делает этот fmap и почему это имеет смысл.

Надеюсь, что кто-то может дать мне подсказка.

Спасибо!

1 Ответ

2 голосов
/ 14 февраля 2020

С учетом парсера p, fmap fn p создаст новый парсер, который анализирует тот же текст, что и p, но затем применяет fn к выводу. Например, если у вас есть синтаксический анализатор parseOptionalNumber :: Parser (Maybe Int), вы можете превратить его в parseNumber :: Parser Int, выполнив parseNumber = fmap fromJust parseOptionalNumber (хотя вы не захотите этого делать, поскольку fromJust является частичным).

Что касается реализации, она работает следующим образом:

  • Все это заключено в Parser $ \s -> …, что создает новый синтаксический анализатор, который выполняет … с учетом входной строки s.
  • parse p s использует функцию parse :: Parser a -> (String -> Maybe (a,String)) (из определения Parser a), чтобы запустить синтаксический анализатор ввода p для строки ввода s, создавая вывод типа Maybe (a,String).
  • (<$>) является синонимом функции fmap, но как оператор, а не функция. Он отображает функцию слева на вывод Maybe (a,String) справа. Функция, которую она отображает, - \(a,c) -> (f a, c), которая запускает данную функцию f над выводом (a,c) из данного синтаксического анализатора p.

Надеюсь, это имеет смысл; если этого не произойдет, может оказаться более полезным переписать fmap в менее компактную форму: 

instance Functor Parser where
    fmap f inParser = Parser $ \inputStr ->
        case (parse inParser inputStr) of
            Nothing -> Nothing
            Just (result, leftoverString) -> Just (f result, leftoverString)
...