4

我有这个单子对象。

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是一个Parserwith parameter Char，我的第一个猜测是c存储这样一个对象。但是经过一秒钟的思考，我知道现在do符号不起作用，你没有得到 monad，你得到了 monad 的内容。太好了，但那告诉我c就是功能

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

但显然这是错误的，因为定义的下一行sat视为c一个角色。这不仅不是我所期望的，而且它的结构比我所期望的低了三个级别！不是函数，不是Maybe对象，也不是元组，而是Just埋在函数内部的元组的左坐标！那个小角色是怎么在外面工作的？是什么指示<-提取单子的这一部分？

4

2 回答 2

3

正如评论所提到的，<-只是做符号语法糖，相当于：

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

所以，我们现在可以用 Char 替换ain (>>=)，给出

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

现在\c->if p c then return c else failParse也有类型：(Char -> Parser b)

Char也是如此c，整个表达式可以扩展为：

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)
于 2018-11-08T07:05:38.333 回答
2

TL;DR：一般来说，根据 Monad 定律，

do { item }

是相同的

do { c <- item
   ; return c
   }

所以它在某种意义上是由 a 定义的。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

IE

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应该清楚了：cforproduced by item（即输入中的第一个字符，如果输入非空），如果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 }
于 2018-11-08T07:59:11.550 回答