Haskell `do` 符号在未由 return 定义时如何知道要取哪个值？

Question

我有这个 monadic 对象。

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

有人告诉我 "reads in a character" 我有一个 item 的定义，但我真的没有看到任何阅读。

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

但是好吧，好吧，也许我应该放宽对 "read" 这个词的直译和嘲笑。继续，我有

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

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

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

Answer 1

如评论所述，<- 只是 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

所以，我们现在可以用 Char 替换 (>>=) 中的 a，得到

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)

Answer 2

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

do { item }

与

相同

do { c <- item
   ; return c
   }

所以它在某种意义上是由return定义的。详情如下。

它确实从正在 "read" 的输入字符串中取出一个字符，所以在这个意义上它 "reads"那个角色：

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

即

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的意思应该很清楚了：对于item产生的c（如果输入非空，这是输入的第一个字符），如果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 }

Haskell `do` 符号在未由 return 定义时如何知道要取哪个值？

How does the Haskell `do` notation know which value to take when it isn't defined by a return?

monads

parsing

haskell

do-notation