parsing - 应用仿函数 : <*> and partial application, 它是如何工作的

Question

我正在阅读 Graham Hutton 所著的《Programming in Haskell》一书，但我在理解如何<*> 时遇到了一些问题。并且可以使用偏应用来解析字符串。

我知道pure (+1) <*> Just 2产生Just 3因为pure (+1)产生Just (+1)然后Just (+1) <*> Just 2产生Just (2+1)然后Just 3

但在更复杂的情况下，像这样:

-- Define a new type containing a parser function
newtype Parser a = P (String -> [(a,String)])

-- This function apply the parser p on inp
parse :: Parser a -> String -> [(a,String)]
parse (P p) inp = p inp

-- A parser which return a tuple with the first char and the remaining string
item :: Parser Char
item = P (\inp -> case inp of
    []     -> []
    (x:xs) -> [(x,xs)])

-- A parser is a functor
instance Functor Parser where
  fmap g p = P (\inp -> case parse p inp of
    []              -> []
    [(v, out)]      -> [(g v, out)])

-- A parser is also an applicative functor
instance Applicative Parser where
  pure v = P (\inp -> [(v, inp)])
  pg <*> px = P (\inp -> case parse pg inp of
    []              -> []
    [(g, out)]      -> parse (fmap g px) out)

所以，当我这样做时:

parse (pure (\x y -> (x,y)) <*> item <*> item) "abc"

答案是:

[(('a','b'),"c")]

但我不明白到底发生了什么。第一:

pure (\x y -> (x,y)) => P (\inp1 -> [(\x y -> (x,y), inp1)])

我现在有了一个只有一个参数的解析器。

然后:

P (\inp1 -> [(\x y -> (x,y), inp1)]) <*> item 
=> P (\inp2 -> case parse (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of ??? 

我真的不明白这里发生了什么。有人可以逐步解释一下现在直到最后发生了什么吗？

Answer 1

让我们评估一下pure (\x y -> (x,y)) <*> item 。第二次申请<*>一旦我们看到第一个就会很容易:

P (\inp1 -> [(\x y -> (x,y), inp1)]) <*> item 

我们替换 <*>表达式及其定义，用表达式的操作数替换定义的参数。

P (\inp2 -> case parse P (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of
    []              -> []
    [(g, out)]      -> parse (fmap g item) out)

然后我们对 fmap 执行相同的操作表达。

P (\inp2 -> case parse P (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of
    []              -> []
    [(g, out)]      -> parse P (\inp -> case parse item inp of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]) out)

现在我们可以减少前两个parse表达式(我们将把 parse item out 留到后面，因为它基本上是原始的)。

P (\inp2 -> case [(\x y -> (x,y), inp2)] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)])

pure (\x y -> (x,y)) <*> item就这么多了。由于您通过提升 a -> b -> (a, b) 类型的二进制函数创建了第一个解析器，对 Parser Char 类型的解析器的单个应用程序表示 Parser (b -> (Char, b)) 类型的解析器.

<小时/>

我们可以通过 parse 运行这个解析器带输入的函数 "abc" 。由于解析器的类型为 Parser (b -> (Char, b)) ，这应该减少为 [(b -> (Char, b), String)] 类型的值。现在让我们评估该表达式。

parse P (\inp2 -> case [(\x y -> (x,y), inp2)] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]) "abc"

根据 parse 的定义这减少到

case [(\x y -> (x,y), "abc")] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]

显然，模式在第一种情况下不匹配，但在第二种情况下匹配。我们用匹配项替换第二个表达式中的模式。

case parse item "abc" of
    []              -> []
    [(v, out)]      -> [((\x y -> (x,y)) v, out)]

现在我们终于评估了最后一个 parse表达。 parse item "abc"明显减少为 [('a', "bc")]根据 item 的定义.

case [('a', "bc")] of
    []              -> []
    [(v, out)]      -> [((\x y -> (x,y)) v, out)]

同样，第二个模式匹配，我们进行替换

[((\x y -> (x,y)) 'a', "bc")]

减少为

[(\y -> ('a', y), "bc")] :: [(b -> (Char, b), String)] -- the expected type

<小时/>

如果您应用相同的过程来评估第二个 <*>应用程序，并将结果放入 parse (结果)"abc"表达式，你会发现表达式确实简化为 [(('a','b'),"c")] .