应用函子：<*> 和部分应用，它是如何工作的

我正在看书Haskell 编程作者：格雷厄姆·赫顿（Graham Hutton），我有一些问题不明白如何<*>部分应用程序可用于解析字符串。

我知道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)])

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

Then:

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

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

我们来评价一下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")].