应用函子：*和部分应用程序，它是如何工作的 [英] applicative functor: <*> and partial application, how it works

问题描述

我正在阅读Graham Hutton编写的一书，并且我有一些问题需要理解<> 和部分应用程序可以用来解析一个字符串。

我知道 pure（+1）*<只有2
产生只需3
，因为纯（+1）产生 Just（+1），然后 Just（+1）*<只是2
产生 Just（2 + 1），然后只是3

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

   -  Define一个包含解析器函数的新类型
 newtype解析器a = P（String  - > [（a，String）]）
 
  - 此函数将解析器p应用于inp 
 parse :: Parser a  - >字符串 - > [（a，String）] 
解析（p p）inp = p inp 
 
  - 一个解析器，返回带有第一个字符和剩余字符串的元组
 item： ：解析器Char 
 item = P（\inp  - > case $ in 
 []  - > [] 
（x：xs） - > [（x，xs）] ）
 
  - 解析器是一个仿函数
实例函数解析器其中
 fmap gp = P（\inp  - > case parse p inp of 
 [] - > [] 
 [（v，out）]  - > [（gv，out）]）
 
  - 解析器也是应用函子
实例解析器，其中
纯v = P（\inp-> [（v，inp）]）
 pg * px = P（\inp  - > case解析pb inp of 
 []  - > [] 
 [（g，out）]  - > parse（fmap g px）out）
  

所以，当我这样做时：

  parse（pure（\xy->（x，y））* item * item）abc
  
 
 
 
答案是：
  [（（' a'，'b'），c）] 
  
但我不明白究竟是什么发生。 
首先：
 
 
  pure（\ x y  - >（x，y））=> P（\inp1-> [（\ xy  - >（x，y），inp1）]）
  
我现在有一个带有一个参数的解析器。
 
 
 
然后： 
 
 
 < （c 1，c 2，...，c 2，...，c 1） item 
 => P（\inp2  - > case parse（\inp1  - > [（\xy  - >（x，y），inp1）]）inp2 
  
我真的不明白这里会发生什么。
有人可以一步一步解释发生了什么，直到最后结束。 / p> 
 
解决方案
我们来评估 pure（\xy->（x，y））* ; item 。第二个应用程序<> 在我们看到第一个应用程序后很容易：
  P（\inp1  - > [（\ xy  - >（x，y），inp1）]）* item b $ b  
我们将<> 表达式在定义时，用表达式的操作数代替定义的参数。
  P（\inp2  - > case parse P（\\ inp1  - > [（\ xy  - >（x，y），inp1）]）inp2 of 
 []  - > [] 
 [（g，out）]  - >解析（fmap g item）out）
  
然后我们对 fmap 表达式也是这样。
  P（\ inp2  - > （\ inp1  - > [（\ x y  - >（x，y），inp1）]）inp2中的
 []  - > [] 
 [（g，out）]  - >解析P（\inp  - >事例解析项目inp of 
 []  - > [] 
 [（v，out）]  - > [（gv，out）]）out）
  
现在我们可以减少前两个 parse 表达式（因为它基本上是原始的，所以我们稍后会将解析项目留出来，因为它基本上是原始的）。 
 
 
 <$ c 
 []  - > [] 
 [（g，out，$ c> P（\inp2  - > case [（\xy->（x，y），inp2） ）]>>事例解析项目超出
 []  - > [] 
 [（v，out）]  - > [（gv，out）]）
  
 
 
对于纯的（\xy->（x，y））*项目。由于您通过提取类型为 a  - >的二元函数创建了第一个解析器， b  - > （a，b），类型为 Parser Char 的解析器的单个应用程序表示类型为 Parser（b - >（char，b））。
 
 
 
 
 
 
我们可以通过 parse 函数输入abc。由于解析器的类型为 Parser（b  - >（Char，b）），所以这应该减少为 [（b  - > ;（Char，b），String）] 。 
 解析P（\inp2  - > case [（\xy  - >（x 
 []  - > [] 
 [（g，out）]  - >案例解析项目超出
 []  - > [] 
 [（v，out）]  - > [（gv，out）]）abc
  
通过定义 parse ，这会降低到
  case [ （\ xy  - >（x，y），abc）]的
 []  - > [] 
 [（g，out）]  - >案例解析项目超出
 []  - > [] 
 [（v，out）]  - > [（gv，out）] 
  
显然，模式在第一种情况下不匹配，但他们在第二种情况下做。 
 案例分析项目abcof 
 []  - > [] 
 [（v，out）]  - > [（（\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\）我们最后评估了最后一个 parse 表达式。 解析项目abc明确减少到 [（'a'，bc）]  code> item 。
  case [（'a'，bc）] 
 []  - > [] 
 [（v，out）]  - > [（（\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\） ，第二个模式匹配，我们做替换
  [（（\xy  - >（x，y））'a '，'bc'）] 
  
减少到
 
 
  [（\ y  - >（'a'，y），bc）] :: [（b  - >（Char，b） ]  - 预期类型
  
 
 
 
 
 
 
如果您应用此选项相同的过程来评估第二个<> 应用程序，并将结果放入 parse  code>abc表达式，你会发现表达式确实减少到 [（（'a'，'b'），c）] 。
 
I am reading the book Programming in Haskell by Graham Hutton and I have some problem to understand how <*> and partial application can be used to parse a string.

I know that pure (+1) <*> Just 2
produces  Just 3
because pure (+1) produces Just (+1) and then Just (+1) <*> Just 2
produces Just (2+1) and then Just 3

But in more complex case like this:
-- 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)
So, when I do:
parse (pure (\x y -> (x,y)) <*> item <*> item) "abc"
The answer is:
[(('a','b'),"c")]
But I don't understand what exactly happens.
First:
pure (\x y -> (x,y)) => P (\inp1 -> [(\x y -> (x,y), inp1)])
I have now a parser with one parameter.

Then:
P (\inp1 -> [(\x y -> (x,y), inp1)]) <*> item 
=> P (\inp2 -> case parse (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of ??? 
I really don't understand what happens here.
Can someone explain, step by step, what's happens now until the end please.
解决方案
Let's evaluate pure (\x y -> (x,y)) <*> item. The second application of <*> will be easy once we've seen the first:
P (\inp1 -> [(\x y -> (x,y), inp1)]) <*> item 
We replace the <*> expression with its definition, substituting the expression's operands for the definition's parameters.
P (\inp2 -> case parse P (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of
    []              -> []
    [(g, out)]      -> parse (fmap g item) out)
Then we do the same for the fmap expression.
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)
Now we can reduce the first two parse expressions (we'll leave parse item out for later since it's basically primitive).
P (\inp2 -> case [(\x y -> (x,y), inp2)] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)])
So much for pure (\x y -> (x,y)) <*> item. Since you created the first parser by lifting a binary function of type a -> b -> (a, b), the single application to a parser of type Parser Char represents a parser of type Parser (b -> (Char, b)).



We can run this parser through the parse function with input "abc". Since the parser has type Parser (b -> (Char, b)), this should reduce to a value of type [(b -> (Char, b), String)]. Let's evaluate that expression now.
parse P (\inp2 -> case [(\x y -> (x,y), inp2)] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]) "abc"
By the definition of parse this reduces to
case [(\x y -> (x,y), "abc")] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]
Clearly, the patterns don't match in the first case, but they do in the second case. We substitute the matches for the patterns in the second expression.
case parse item "abc" of
    []              -> []
    [(v, out)]      -> [((\x y -> (x,y)) v, out)]
Now we finally evaluate that last parse expression. parse item "abc" clearly reduces to [('a', "bc")] from the definition of item.
case [('a', "bc")] of
    []              -> []
    [(v, out)]      -> [((\x y -> (x,y)) v, out)]
Again, the second pattern matches and we do substitution
[((\x y -> (x,y)) 'a', "bc")]
which reduces to
[(\y -> ('a', y), "bc")] :: [(b -> (Char, b), String)] -- the expected type




If you apply this same process to evaluate a second <*> application, and put the result in the parse (result) "abc" expression, you'll see that the expression indeed reduces to[(('a','b'),"c")].

                        
这篇关于应用函子：*和部分应用程序，它是如何工作的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！