Question

TL; DR

Я пытаюсь понять, как это:

satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = PsrOf p
  where
    p (c:cs) | pred c = Just (cs, c)
    p _ = Nothing

Эквивалентно этому:

satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = do
    c <- anyChar
    if pred c then return c else empty

Контекст

Это фрагмент некоторых лекционных заметок о разборе языка Haskell, которые я пытаюсь понять:

import Control.Applicative
import Data.Char
import Data.Functor
import Data.List

newtype Parser a = PsrOf (String -> Maybe (String, a))
    -- Function from input string to:
    --
    -- * Nothing, if failure (syntax error);
    -- * Just (unconsumed input, answer), if success.

dePsr :: Parser a -> String -> Maybe (String, a)
dePsr (PsrOf p) = p

-- Monadic Parsing in Haskell uses [] instead of Maybe to support ambiguous
-- grammars and multiple answers.

-- | Use a parser on an input string.
runParser :: Parser a -> String -> Maybe a
runParser (PsrOf p) inp = case p inp of
                            Nothing -> Nothing
                            Just (_, a) -> Just a
                          -- OR: fmap (\(_,a) -> a) (p inp)

-- | Read a character and return. Failure if input is empty.
anyChar :: Parser Char
anyChar = PsrOf p
  where
    p "" = Nothing
    p (c:cs) = Just (cs, c)

-- | Read a character and check against the given character.
char :: Char -> Parser Char
-- char wanted = PsrOf p
--   where
--     p (c:cs) | c == wanted = Just (cs, c)
--     p _ = Nothing
char wanted = satisfy (\c -> c == wanted)   -- (== wanted)

-- | Read a character and check against the given predicate.
satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = PsrOf p
  where
    p (c:cs) | pred c = Just (cs, c)
    p _ = Nothing
-- Could also be:
-- satisfy pred = do
--     c <- anyChar
--     if pred c then return c else empty

instance Monad Parser where
    -- return :: a -> Parser a
    return = pure

    -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    PsrOf p1 >>= k = PsrOf q
      where
        q inp = case p1 inp of
                  Nothing -> Nothing
                  Just (rest, a) -> dePsr (k a) rest

Я все понимаю до последнего бита определения Monad, в частности, я не понимаю, как следующая строка возвращает что-то типа Parser b, как того требует определение (>>=):

Just (rest, a) -> dePsr (k a) rest

Мне трудно понять, что означает определение Монады без примера. К счастью, у нас есть одна в альтернативной версии функции satisfy, которая использует do-нотацию (что, конечно, означает, что вызывается Monad). Я действительно не понимаю do-обозначения, так что вот десагаред версия satisfy:

satisfy pred = do
    anyChar >>= (c ->
    if pred c then return c else empty)

Итак, основываясь на первой строке нашего (>>=) определения, которое

PsrOf p1 >>= k = PsrOf q

У нас anyChar как наши PsrOf p1 и (c -> if pred c then return c else empty) как наши k. Чего я не понимаю, так это то, как в dePsr (k a) rest, когда (k a) возвращает Parser (по крайней мере, оно будет скрыто, иначе вызов dePsr не будет иметь смысла). Это делает более запутанным присутствие rest. Даже если (k a) вернул Parser, вызов dePsr извлечет основную функцию из возвращенного Parser и передаст ей rest в качестве ввода. Это определенно не возвращает что-то типа Parser b, как того требует определение (>>=). Я явно что-то не так понимаю.

John F. Miller · Answer 1 · 05 апреля 2019

ок, может это поможет. Давайте начнем с того, что вернем некоторые точки обратно в dePsr.

dePsr :: Parser a -> String -> Maybe (String, a)
dePsr (PsrOf p) rest = p rest

И давайте также выпишем возвращение: (NB я добавляю все пункты для ясности)

return :: a -> Parser a
return a = PsrOf (\rest -> Just (rest, a))

А теперь из Just ветви (>>=) определения

 Just (rest, a) -> dePsr (k a) rest

Давайте удостоверимся, что мы согласны с тем, что каждая вещь:

rest строка, оставшаяся непарсированной после применения p1
a Результат применения p1
k :: a -> Parser b берет результат предыдущего парсера и создает новый парсер
dePsr разворачивает Parser a обратно в функцию `String -> Maybe (String, a)

Помните, что мы обернем это обратно в синтаксический анализатор в верхней части функции: PsrOf q

Таким образом, в английском языке bind (>>=) принимает синтаксический анализатор в a и функцию из a в синтаксический анализатор в b и возвращает синтаксический анализатор в b. Полученный синтаксический анализатор создается путем переноса q :: String -> Maybe (String, b) в конструктор Parser PsrOf. Затем q, объединенный синтаксический анализатор, принимает String, называемый inp, и применяет функцию p1 :: String -> Maybe (String,a), которую мы получили из сопоставления с образцом, к первому анализатору, и сопоставление с образцом в результате. За ошибку выкладываем Nothing (легко). Если у первого парсера был результат, у нас есть буксируемые фрагменты информации, еще непарсированная строка с именем rest и результат a. Мы даем a на k, второй комбинатор синтаксического анализатора, и получаем Parser b, который нам нужно развернуть с помощью dePsr, чтобы получить функцию (String -> Maybe (String,b) назад. Эту функцию можно применить к rest для окончательный результат комбинированных парсеров.

Я думаю, что самое сложное в чтении это то, что иногда мы карри выполняем функцию синтаксического анализа, которая скрывает то, что на самом деле происходит.

Хорошо для satisfy примера

satisfy pred 
  = anyChar >>= (c -> if pred c then return c else empty)

empty происходит из альтернативного экземпляра и является PsrOf (const Nothing), поэтому анализатор всегда завершается ошибкой.

Давайте посмотрим только на успешные ветки. Подменой только удачной части:

PsrOf (\(c:cs) ->Just (cs, c)) >>= (\c -> PsrOf (\rest -> Just (rest, c)))

Так что в связке (>>=) определение

p1 = \(c:cs -> Just (cs, c))
k = (\c -> PsrOf (\rest -> Just (rest, c)))
q inp = let Just (rest,a) = p1 inp in dePsr (k a) rest снова только удачная ветка

Тогда q становится

q inp = 
  let Just (rest, a) = (\(c:cs) -> Just (cs, c)) inp
   in dePsr (\c -> PsrOf (\rest -> Just (rest, c))) a rest

Делаем небольшое β-сокращение

q inp =
 let (c:cs) = inp
     rest = cs
     a = c
  in dePsr (PsdOf (\rest -> Just (rest, a))) rest -- dePsr . PsrOf = id

Наконец-то убираю еще

q (c:cs) = Just (cs, c)

Таким образом, если pred успешен, мы уменьшаем satisfy до точно anyChar, что является именно тем, что мы ожидаем, и именно то, что мы находим в первом примере вопроса. Я оставлю это как и укажу читателю (читай: я ленивый), чтобы доказать, что если inp = "" или pred c = False, то результат будет Nothing, как в первом satisfy примере.

ПРИМЕЧАНИЕ. Если вы делаете что-то кроме назначения класса, вы сэкономите часы боли и разочарования, начав с обработки ошибок с самого начала, чтобы ваш синтаксический анализатор String -> Either String (String,a) легко сделал тип ошибки более общим позже , но PITA, чтобы изменить все с Maybe на Either.

Вопрос:"[C] не могли бы вы объяснить, как вы пришли к return a = PsrOf (\rest -> Just (rest, a)) из return = pure после того, как вы вернули« очки »обратно?

Ответ: Прежде всего, довольно неудачно дать определение экземпляра Monad без определений Functor и Applicative. Функции pure и return должны быть идентичны (это является частью законов Монады), и их можно было бы назвать одним и тем же, за исключением Monad, значительно предшествовавшего Applicative в истории Haskell. На самом деле, я не «знаю», как выглядит чистый, но я знаю, что это должно быть, потому что это единственно возможное определение. (Если вы хотите понять доказательство этого утверждения, я прочитал документы и знаю результаты, но мне не достаточно набранных лямбда-исчислений, чтобы быть уверенными в воспроизведении результатов.)

return должен переносить значение в контексте без изменения контекста.

return :: Monad m => a -> m a
return :: a -> Parser a -- for our Monad
return :: a -> PsrOf(\str -> Maybe (rest, value)) -- substituting the constructor (PSUDO CODE)

A Parser - это функция, которая принимает строку для анализа и возвращает Just значение вместе с любой непарсированной частью исходной строки или Nothing on failure, all wrapped in the constructor PsrOf . The context is the string to be parsed, so we cannot change that. The value is of course what was passed to return`.Синтаксический анализатор всегда завершается успешно, поэтому мы должны вернуть только значение.

return a =  PsrOf (\rest -> Just (rest, a))

rest - это контекст, и он передается без изменений.a - это значение, которое мы помещаем в контекст Monad.

Для полноты здесь также есть единственное разумное определение fmap из Functor.

fmap :: Functor f => (a->b) -> f a -> f b
fmap :: (a -> b) -> Parser a -> Parser b -- for Parser Monad
fmap f (PsrOf p) = PsrOf q
  where q inp = case p inp of
    Nothing -> Nothing
    Just (rest, a) -> Just (rest, f a)
  -- better but less instructive definition of q
  -- q = fmap (\(rest,a) -> (rest, f a)) . p

Использование монады для простого парсера Haskell

TL; DR

Контекст

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

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

Использование монады для простого парсера Haskell

TL; DR

Контекст

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

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

Похожие темы