Как нотация `do` в Haskell узнает, какое значение нужно принять, если оно не определено возвратом?

У меня есть этот монадический объект.

data Parser a = Parser (String -> Maybe (a, String))

instance Functor Parser where
  -- fmap :: (a -> b) -> Parser a -> Parser b
  fmap f (Parser pa) =  Parser $ \input -> case pa input of
                                             Nothing -> Nothing
                                             Just (a, rest) -> Just (f a, rest)

instance Applicative Parser where
  pure = return
  (<*>) = ap

instance Monad Parser where
  --return :: a -> Parser a
  return a =  Parser $ \input -> Just (a, input)

  --(>>=) :: Parser a -> (a -> Parser b) -> Parser b
  (Parser pa) >>= f  = Parser $ \input -> case pa input of
                                            Nothing -> Nothing
                                            Just (a,rest) -> parse (f a) rest

И у меня есть это определение item, которое, как мне говорят, «читается в символе», но я действительно не вижу никакого чтения.

item :: Parser Char
item = Parser $ \ input -> case input of ""    -> Nothing
                                         (h:t) -> Just (h, t)

Но ладно, ладно, может быть, я должен просто расслабиться, говоря о том, насколько буквально понимать слово «читать» и подшучивать над ним. Идем дальше, у меня есть

failParse :: Parser a
failParse = Parser $ \ input -> Nothing

sat :: (Char -> Bool) -> Parser Char
sat p = do c <- item
           if p c
           then return c
           else failParse

И тут я совсем запутался. Что хранится в переменной c? Поскольку item — это Parser с параметром Char, мое первое предположение состоит в том, что c хранит такой объект. Но после секундного размышления я понимаю, что теперь не работает нотация do, вы не получаете монаду, вы получаете содержимое монады. Отлично, но тогда это говорит мне, что c - это функция

\ input -> case input of ""    -> Nothing
                         (h:t) -> Just (h, t)

Но очевидно, что это неправильно, так как следующая строка определения sat рассматривает c как символ. Мало того, что это не то, что я ожидал, но это примерно на три уровня структуры ниже, чем я ожидал! Это не функция, не объект Maybe и не кортеж, а левая координата кортежа Just, спрятанная внутри функции! Как этот маленький персонаж работает так далеко снаружи? Что указывает <- извлечь эту часть монады?


parsing haskell monads do-notation
person Addem    schedule 08.11.2018    source источник
comment
сделайте нотацию просто синтаксическим сахаром, де-сахар ваш случай: item ››= (\c-›if p c then return c else failParse). см.: [ссылка] (en.wikibooks.org/wiki/Haskell/do_notation)   -  person assembly.jc    schedule 08.11.2018

Ответы (2)


arrow_upward
3
arrow_downward

Как упоминалось в комментарии, <- просто будет do notation синтаксическим сахаром и эквивалентно:

item >>= (\c->if p c 
              then return c 
              else failParse)

Хорошо, давайте посмотрим, что такое c? рассмотрим определение (>>=)

(>>=) :: Parser a -> (a -> Parser b) -> Parser b

или более читаемый способ:

Parser a >>= (a -> Parser b)

И теперь, сопоставляя его с приведенным выше выражением item >>= (\c->if p c then return c else failParse), дайте:

Parer a = item

а также

(a->Parser b) = (\c->if p c then return c else failParse)

и item имеет тип:

item :: Parser Char

Итак, теперь мы можем заменить a в (>>=) на Char, что дает

Parser Char >>= (Char -> Parser b)

и теперь \c->if p c then return c else failParse также имеют тип: (Char -> Parser b)

и поэтому c является Char, и все выражение можно расширить до:

sat p =
item >>= (\c->...) = 
Parser pa >= (\c->...) = Parser $ \input -> case pa input of
                                            Nothing -> Nothing
                                            Just (a,rest) -> parse (f a) rest
                         where f c =  if p c
                                      then return c
                                      else failParse
                               pa input = case input of ""   -> Nothing
                                                       (h:t) -> Just (h, t)
person assembly.jc    schedule 08.11.2018
comment
@WillNess, возможно, вы правы, параметр c в (\c-›...), наконец, заменяется выводом функции внутри элемента (т.е. pa в Parser pa). но если pa возвращает Nothing, (\c-›...) не будет применяться, поэтому семантически мы не можем сказать c == Nothing, поскольку c никогда не заменяется ничем. Итак, я не придаю никакого значения (‹-), так как фактическое значение должно относиться к определению (››=). Но для точности я удалю из своего ответа термин «ничего не извлекать». - person assembly.jc; 08.11.2018
comment
Да, поэтому ‹- в конечном итоге заменяется на ››=, выражение ниже ‹- становится функцией справа от ››=, а c слева от ‹- становится параметром функции. и так, что ‹- делать? - person assembly.jc; 08.11.2018
comment
извлекает значение. - person Will Ness; 08.11.2018
comment
В порядке Хорошо. но я все же предпочитаю переводить ‹- в ››= и смотреть, как ››= определяется в конкретном случае. Это точность и однозначность. - person assembly.jc; 08.11.2018

arrow_upward
2
arrow_downward

TL;DR: В общем, по законам монад,

do { item }

такой же как

do { c <- item
   ; return c
   }

поэтому он в некотором смысле определяется return. Подробности следуют.

Он берет один символ из входной строки, которая читается, поэтому в этом смысле он читает этот символ:

item :: Parser                                   Char
item = Parser $ \ input ->          -- input :: [Char]   
             case input of { ""    -> Nothing
                           ; (h:t) -> Just (h, t)  -- (h:t) :: [Char]
                           }             -- h :: Char    t  :: [Char]

и я уверен, что есть определение

parse (Parser pa) input = pa input

определено там где-то; так

parse item input = case input of { ""    -> Nothing 
                                 ; (h:t) -> Just (h, t) }

Далее, что означает (>>=)? Это означает, что

parse (Parser pa >>= f) input = case (parse (Parser pa) input) of
                     Nothing             -> Nothing
                     Just (a, leftovers) -> parse (f a) leftovers

i.e.

parse (item      >>= f) input
      = case (parse  item  input) of
                     Nothing             -> Nothing
                     Just (a, leftovers) -> parse (f a) leftovers
      = case (case input of { "" -> Nothing 
                            ; (h:t) -> Just (h, t) 
                            }) of
                     Nothing             -> Nothing
                     Just (a, leftovers) -> parse (f a) leftovers
      = case input of 
           ""    ->                         Nothing 
           (h:t) -> case Just (h, t) of {
                         Just (a, leftovers) -> parse (f a) leftovers }
      = case input of 
           ""    -> Nothing 
           (h:t) -> parse (f h) t

В настоящее время,

-- sat p: a "satisfies `p`" parser 
sat :: (Char -> Bool) -> Parser Char
sat p = do { c <- item           -- sat p :: Parser Char
           ; if p c              -- item  :: Parser Char,  c :: Char
                then return c    -- return c  :: Parser Char
                else failParse   -- failParse :: Parser Char
           }
      = item >>= (\ c ->
                    if p c then return c else failParse)

(путем раскрытия синтаксиса do) и т.д.

parse (sat p) input 
 = parse (item >>= (\ c ->
                    if p c then return c else failParse)) input
   -- parse (item >>= f) input
   --  = case input of { "" -> Nothing ; (h:t) -> parse (f h) t }
 = case input of 
       ""    -> Nothing 
       (h:t) -> parse ((\ c -> if p c then (return c)
                                       else failParse) h) t
 = case input of 
       ""    -> Nothing 
       (c:t) -> parse (if p c then (return c) 
                               else failParse) t
 = case input of 
       ""    -> Nothing 
       (c:t) -> if p c then parse (return c) t
                               else parse failParse t
 = case input of 
       ""    -> Nothing 
       (c:t) -> if p c then Just (c, t)
                               else Nothing

Теперь значение sat p должно быть ясным: для c, созданного item (который является первым символом во входных данных, если input не пуст), если p c выполняется, c принимается и синтаксический анализ завершается успешно, в противном случае синтаксический анализ завершается неудачей:

sat p = for c from item:                 -- do { c <- item 
           if p c                        --    ; if p c
                then return c            --        then return c 
                else failParse           --        else failParse }
person Will Ness    schedule 08.11.2018