Haskell：Graham Hutton图书解析（Ch-8）：解析（f v）的功能是什么，以及它是如何做到的？

问题描述 投票：2回答：3

我的问题是关于Graham Hutton的书Programming in Haskell 1st Ed。

[在第8.4节中创建了一个解析器，我假设所有回答的人都有书，或者可以在上面的链接中看到幻灯片8的链接。

称为item的基本解析器描述为：

type Parser a = String -> [(a, String)]

item :: Parser Char

item = \inp -> case inp of
        [] -> []
        (x:xs) -> [(x,xs)]

与do一起使用以定义另一个解析器p（do解析器）

p :: Parser (Char, Char)

p = do x <- item
       item
       y <- item
       return (x,y)

相关的绑定定义为：

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

p >>= f = \inp -> case parse p inp of
                       [] -> []
                       [(v,out)] -> parse (f v) out

return定义为：

return  :: a -> Parser a

return v = \inp -> [(v,inp)]

parse定义为：

parse :: Parser a -> String -> [(a,String)]

parse p inp = p inp

程序（do解析器）获取一个字符串，并选择第一个和第三个字符，然后以元组的形式返回它们，并将字符串的其余部分显示在列表中，例如，"abcdef"产生[('a','c'), "def"]。

我想知道(f v) out在[(v,out)] -> parse (f v) out返回解析器，然后将其应用于out。

  • f解析器中的do是item，并且item带有字符'c'返回[('c',[])]？

  • 那怎么可能是解析器，如何将out作为参数？

也许我只是不了解(f v)的作用。

  • 并且do解析器每次再次调用item时，如何“丢弃”返回的值以对其余的输入字符串进行运算？

  • 通过do解析器工作的对象是什么，如何在每个步骤进行更改，以及通过什么方法进行更改？

parsing haskell monads
3个回答
4
投票

f v产生Parser b，因为f是a -> Parser b类型的函数，而v是a类型的值。因此，您将使用此parse和字符串Parser b作为参数来调用out。

'do'解析器中的F是项目

不，不是。让我们考虑一下解析器的简化版本（尽管现在已经毫无意义）：

p = do x <- item
       return x

这将使糖降低到：

p = item >>= \x -> return x

因此>>=的右操作数，即f是\x -> return x，而不是item。

并且每次再次调用item时，“解析器”如何每次都“丢弃”返回的值以对其余的输入字符串进行操作？通过“ do”解析器起作用的对象是什么？如何对其进行更改，以及每个步骤以及通过什么方法对其进行更改？

当您应用解析器时，它将返回一个元组，其中包含已解析的值和代表其余输入的字符串。例如，如果您查看item，则元组的第二个元素将是xs，它是输入字符串的尾部（即，包含除第一个以外的所有输入字符串字符的字符串）。元组的第二部分将作为新输入馈入后续解析器（按照[(v,out)] -> parse (f v) out），这样，每个后续解析器都将前一个解析器生成的字符串作为输出元组的第二部分作为输入（这将是its输入的后缀）。

根据您的评论：

[当您写“ p = item >> = \ x-> return x”时，是否仅相当于第一行“ p = do x

否，它等于整个do块（即do {x <- item; return x}）。您不能像这样逐行翻译do块。 do { x <- foo; rest }等效于foo >>= \x -> do {rest}，因此，您始终将do块的其余部分作为>>=右操作数的一部分。

但不是减少到简单地将“输出”用作下一行的输入的方式。如果'do'解析器的下一行是项解析器，解析该怎么做？

让我们来看一个示例，在该示例中，我们两次调用item（就像您的p，但没有中间的项）。在下面，我将使用===表示===上方和下方的表达式是等效的。

do x <- item
   y <- item
   return (x, y)
=== -- Desugaring do
item >>= \x -> item >>= \y -> return (x, y)
=== -- Inserting the definition of >>= for outer >>=
\inp -> case parse item inp of
             [] -> []
             [(v,out)] -> parse (item >>= \y -> return (v, y)) out

现在让我们将其应用于输入“ ab”：

case parse item "ab" of
     [] -> []
     [(v,out)] -> parse (item >>= \y -> return (v, y)) out
=== Insert defintiion of `parse`
case item "ab" of
     [] -> []
     [(v,out)] -> parse (item >>= \y -> return (v, y)) out
=== Insert definition of item
case ('a', "b") of
     [] -> []
     [(v,out)] -> parse (item >>= \y -> return (v, y)) out
===
parse (item >>= \y -> return ('a', y)) out

现在我们可以像拳头一样展开第二个>>=，最后得到('a', 'b')。

2
投票

相关建议是，不要惊慌（意味着，不要着急；或者，慢慢来），然后，跟随类型。

首先是Parser s

type Parser a = String -> [(a,String)]

are函数从String到a类型的结果值对和剩余字符串的配对列表（因为type定义了类型同义词，而不是像data或newtype这样的新类型） 。

该leftovers字符串将用作next解析步骤的input。这就是这里的主要内容。

您在问，in

p >>= f = \inp -> case (parse p inp) of
                       [] -> []
                       [(v,out)] -> parse (f v) out

(f v)中的[(v,out)] -> parse (f v) out如何返回解析器，然后将其应用于out？

答案是，f的type表示这样做：

(>>=) :: Parser a -> (a -> Parser b) -> Parser b    -- or, the equivalent
(>>=) :: Parser a -> (a -> Parser b) -> (String -> [(b,String)])
--       p              f                inp

我们有f :: a -> Parser b，所以这就是它的作用：应用于a类型的值，它返回Parser b类型的值。或等效地，

f    :: a       -> (String  -> [(b,String)])      -- so that
f (v :: a)      ::  String  -> [(b,String)]       -- and,
f (v :: a) (out ::  String) :: [(b,String)]

所以parse p inp 产生]的值是多少，它必须是f等待进行的操作。类型必须“ fit”：

      p :: Parser a                     --   m  a
f       ::        a -> Parser b         --      a -> m  b
f <$> p :: Parser    ( Parser b )       --   m     ( m  b )
f =<< p :: Parser             b         --   m          b

或等效地，
p       :: String -> [(a,   String)]
--         inp         v    out
      f ::             a -> String   -> [(b, String)]
--                     v    out
p >>= f :: String                    -> [(b, String)]     -- a combined Parser
--         inp                            v2  out2

所以这也回答了您的第二个问题，

这怎么可能是一个解析器，如何将out作为参数？

真正的问题是，这是哪种f，这件事吗？它从何而来？这是你的第四个问题。

答案是，您的示例使用do-符号，

p :: Parser (Char, Char)

p = do x <- item
       _ <- item
       y <- item
       return (x,y)

根据Monad法则等效于嵌套链
p = do { x <- item
       ; do { _ <- item
            ; do { y <- item
                 ; return (x,y) }}}

这是Parser bind
应用程序的嵌套链的语法糖，
p :: Parser (Char, Char) -- ~ String -> [((Char,Char), String)]

p = item >>= (\ x ->              -- item :: Parser Char ~ String -> [(Char,String)] 
               item >>= (\ _ ->                      -- x :: Char
                          item >>= (\ y ->           -- y :: Char
                                     return (x,y) )))

并且是因为
嵌套函数，使得最终的return可以访问bothyand x；而正是Parser bind安排输出的剩余字符串用作下一解析步骤的输入：
p = item >>= f     -- :: String -> [((Char,Char), String)]
    where    
           { f x = item >>= f2
                    where { f2 _ = item >>= f3
                                    where { f3 y = return (x,y) }}}

即（假设inp是长度为2或更长的字符串），>
parse p inp                            -- assume that `inp`'s 
  = (item >>= f) inp                   --  length is at least 2     NB.
  =
    let  [(v, left)] = item inp        -- by the def of >>=
    in                                
        (f v) left
  =
    let  [(v, left)] = item inp
    in
       let  x = v                      -- inline the definition of `f`
       in  (item >>= f2) left
  =
    let  [(v, left)] = item inp
    in let  x = v 
       in let  [(v2, left2)] = item left     -- by the def of >>=, again
          in (f2 v2) left2
  =
    ..........
  =
    let  [(x,left1)] = item inp        -- x <- item
         [(_,left2)] = item left1      -- _ <- item
         [(y,left3)] = item left2      -- y <- item
    in 
        [((x,y), left3)]
  =
    let   (x:left1)  = inp             -- inline the definition
          (_:left2)  = left1           -- of `item`
          (y:left3)  = left2
    in 
        [((x,y), left3)]
  =
    let   (x:_:y:left3) = inp
    in 
        [((x,y), left3)]

经过一些简化。 
这将回答您的第三个问题。

我在阅读语法时遇到类似的问题，因为这不是我们习惯的语法。 

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

p >>= f = \inp -> case parse p inp of
                       [] -> []
                       [(v,out)] -> parse (f v) out

因此提出以下问题：我想知道[[v，out）]-> parse（f v）out中的（f v）如何返回解析器，然后将其应用于out。

这是因为那是第二个arg（f）的标志：（>> =）::解析器a-> （（a->解析器b）

->解析器b ... 。[[f接受a并产生Parser b。一个解析器b接受一个String，它是out ...（f v）out但是此输出不应与我们正在编写的函数的输出混合：

>> =

    我们正在输出解析器...（>> =）::解析器a->（a->解析器b）->
  • 解析器b
。 我们正在输出的解析器具有包装和链接前两个参数的工作
  • 解析器是一个需要1个arg的函数。

    这是在第一个=]之后构造的，即通过返回一个（匿名）函数：p >> = f = \ inp-> ...

    • 所以inp指代我们正在构建的解析器的输入字符串所以剩下的就是定义构造函数应该做什么...

    注意：我们没有实现任何输入分析器，只是将它们链接在一起

     ...所以，输出分析器函数应该     ：
      将输入解析器（
    • p）应用于其输入（inp）：p >> = f = \ inp-> case parse p inp of获取该解析的输出[（v，out）]
    • v
      • 是结果out是输入的剩余内容将输入函数（f为
    • （（a->解析器b）
      • ）应用于解析结果（v）
    f产生一个
  • 解析器b
    • （一个需要1个arg的函数）    因此将输出解析器应用于第一个解析器的
  • remainder
    • （out）    对我来说，理解在于对结构的使用，以及我们正在构造一个将其他功能的执行粘合在一起的功能，而仅考虑它们的接口

    希望有帮助...它帮助我写了：-）

    0
    投票

    我在阅读语法时遇到类似的问题，因为这不是我们习惯的语法。

    最新问题
    © www.soinside.com 2019 - 2024. All rights reserved.