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

Question

我读格雷厄姆·赫顿在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

TL; DR：当你说你“（现在）有一个参数解析器” inp1，你糊涂了：inp1是输入字符串的解析器，但功能(\x y -> (x,y)) - 这只是(,) - 正在应用于输出值（s），通过解析输入字符串生成。通过您的临时解析器产生的值的顺序是：

-- by (pure (,)): 
(,)      -- a function expecting two arguments 

-- by the first <*> combination with (item): 
(,) x     -- a partially applied (,) function expecting one more argument 

-- by the final <*> combination with another (item): 
((,) x) y == (x,y)  -- the final result, a pair of `Char`s taken off the 
         -- input string, first (`x`) by an `item`, 
         -- and the second (`y`) by another `item` parser 

---

工作由等式推理往往更容易：

-- pseudocode definition of `fmap`: 
parse (fmap g p) inp = case (parse p inp) of -- g :: a -> b , p :: Parser a 
    []    -> []      --  fmap g p :: Parser b 
    [(v, out)]  -> [(g v, out)]    -- v :: a ,   g v :: b 

（显然这是假定任何解析器只能生产或结果，因为长列表的情况根本没有处理 - 这通常是皱眉，并有充分的理由）;

-- pseudocode definition of `pure`: 
parse (pure v) inp = [(v, inp)]     -- v :: a , pure v :: Parser a 

（与pure v解析产生v不消耗输入）;

-- pseudocode definition of `item`: 
parse (item) inp = case inp of     -- inp :: ['Char'] 
    []    -> [] 
    (x:xs)   -> [(x,xs)]     -- item :: Parser 'Char' 

（与item装置采取一个Char关闭输入String的头部，如果可能的话解析）;并且，

-- pseudocode definition of `(<*>)`: 
parse (pg <*> px) inp = case (parse pg inp) of -- px :: Parser a 
    []    -> [] 
    [(g, out)]  -> parse (fmap g px) out  -- g :: a -> b 

（<*>结合两个分析器与适合类型的结果，产生一个新的，合并的分析器使用第一解析来解析输入，然后使用第二解析器来解析剩串，结合两个结果产生新的组合解析器的结果）;现在

，<*>同伙向左，所以你问的是

parse (pure (\x y -> (x,y)) <*> item <*> item) "abc" 
= parse ((pure (,) <*> item1) <*> item2) "abc"    -- item_i = item 

最右边<*>是最高的，所以我们扩大它第一，离开嵌套的表达是现在，

= case (parse (pure (,) <*> item1) "abc") of     -- by definition of <*> 
    []    -> [] 
    [(g2, out2)] -> parse (fmap g2 item2) out2 
         = case (parse item out2) of   -- by definition of fmap 
          []    -> [] 
          [(v, out)]  -> [(g2 v, out)] 
         = case out2 of      -- by definition of item 
          []    -> [] 
          (y:ys)   -> [(g2 y, ys)] 

类似地，嵌套表达式简化为

parse (pure (,) <*> item1) "abc" 
= case (parse (pure (\x y -> (x,y))) "abc") of    -- by definition of <*> 
    []    -> [] 
    [(g1, out1)] -> parse (fmap g1 item1) out1 
         = case (parse item out1) of .... 
         = case out1 of 
          []    -> [] 
          (x:xs)   -> [(g1 x, xs)] 
= case [((,), "abc")] of          -- by definition of pure 
    [(g1, out1)] -> case out1 of 
          []    -> [] 
          (x:xs)   -> [(g1 x, xs)] 
= let { out1 = "abc" 
     ; g1 = (,) 
     ; (x:xs) = out1 
     } 
    in [(g1 x, xs)] 
= [((,) 'a', "bc")] 

，因此我们得到

= case [((,) 'a', "bc")] of 
    [(g2, out2)] -> case out2 of 
          []    -> [] 
          (y:ys)   -> [(g2 y, ys)] 

我想你现在可以看到，为什么结果会是[(((,) 'a') 'b', "c")]。

Answer 2

让我们评估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 (b -> (Char, b))类型的解析器。

---

我们可以输入​​运行通过parse功能这个解析器。由于解析器的类型为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"明确地从item的定义减少到[('a', "bc")]。

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（结果）​​expr激情，你会发现表达式确实减少到[(('a','b'),"c")]。

Answer 3

什么帮助了我很多，而学习这些东西的重点是类型涉及的价值和功能。这完全是关于将一​​个函数应用于某个值（或者在您的情况下，将函数应用于两个值值）。

($) ::     (a -> b) -> a -> b 
fmap :: Functor  f => (a -> b) -> f a -> f b 
(<*>) :: Applicative f => f (a -> b) -> f a -> f b 

所以有函子我们在价值应用功能的“容器/上下文”内（即也许，列表，。），并与应用型我们要应用功能本身在“容器/上下文”中。

要应用的函数是(,)，并且您要应用函数的值位于容器/上下文内（在您的案例中为Parser a）。

使用pure我们解除功能(,)到同一个“上下文/容器”我们的价值观是（注意，我们可以使用pure解除功能分为任何应用型（也许，列表分析器。 。）：

(,) ::    a -> b -> (a, b) 
pure (,) :: Parser (a -> b -> (a, b)) 

使用<*>我们可以应用功能(,)，现在是Parser背景下，这也是该Parser上下文中的值内。 +1提供的示例的一个不同之处在于(,)具有两个参数。因此，我们必须使用<*>两次：

(<*>) :: Applicative f => f (a -> b) -> f a -> f b 

x :: Parser Int 
y :: Parser Char 

let p1 = pure (,) <*> x :: Parser (b -> (Int, b)) 
let v1 =  (,)  1 ::   b -> (Int, b) 

let p2 = p1 <*> y :: Parser (Int, Char) 
let v2 = v1 'a' ::  (Int, Char) 

现在，我们已经创建了一个新的解析器（p2），我们可以使用，就像任何其他的解析器！

。 。然后还有更多！

看一看这个方便的功能：

(<$>) :: Functor f => (a -> b) -> f a -> f b 

<$>只是fmap，但你可以用它来多写得很漂亮的组合子：

data User = User {name :: String, year :: Int} 
nameParser :: Parser String 
yearParser :: Parser Int 

let userParser = User <$> nameParser <*> yearParser -- :: Parser User 

好吧，这个答案比我长预期！那么，我希望它有帮助。也许我们也可以看看Typeclassopedia，我发现它是无价的，同时学习Haskell，这是一个无尽美丽的过程。 。 :)

Answer 4

首先，我想强调一件事。我发现理解的核心在于注意到Parser本身与运行解析器parse之间的分隔。

在运行解析器时，您将Parser和输入字符串输入parse，它会给出可能的解析列表。我认为这可能很容易理解。

您将通过parse a Parser，它可以使用胶水<*>构建。试着了解当您通过parse,Parser,a或Parser,f <*> a <*> b时，您会传递相同类型的东西，即相当于(String -> [(a,String)])的东西。我认为这可能很容易理解，但“点击”仍需要一段时间。

这就是说，我会谈一谈这个应用胶的性质，<*>。一个应用，F a是一种计算，产生类型a的数据。你能想到的一个术语，如

... f <*> g <*> h 

的一系列返回一些数据计算的，说a然后b然后c。在Parser的情况下，计算涉及f在当前字符串中查找a，然后将字符串的其余部分传递给g等。如果任何计算/解析失败，那么整个术语也是如此。

它有趣的是，任何应用性可以用一个纯函数开头写入收集所有这些发射值，所以我们一般可以写，

pure3ArgFunction <$> f <*> g <*> h 

我个人认为发射的心智模式和收集有用的。

所以，用了那么长的序言，转到了实际的解释上。

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

是做什么用的？那么，parse (p::Parser (Char,Char) "abc"将解析器（我将其重命名为p）应用于“abc”，产生[(('a','b'),"c")]。这是用（'a'，'b'）和剩余字符串“c”的返回值成功解析的。

好的，那不是问题。为什么解析器以这种方式工作？与开始：

.. <*> item <*> item 

item需要从字符串的下一个字符，它产生作为结果并将未消耗的输入。下一个item也是这样。一开始可以改写为：

fmap (\x y -> (x,y)) $ item <*> item 

或

(\x y -> (x,y)) <$> item <*> item 

这是我表示纯函数没有做任何事情来输入字符串的方式，它只是收集结果。从这个角度来看，我认为解析器应该很容易理解。好简单。太容易了。我的意思是非常严肃。它并不是说这个概念太难了，但是我们看编程的一般框架太过于陌生，一开始就没有多大意义。

Answer 5

嗯我对Haskell没有经验，但是我尝试生成Parser类型的Functor和Applicative实例如下：

-- 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 f) = P (\str -> map (\(x,y) -> (g x, y)) $ f str) 

-- A parser is also an applicative functor 
instance Applicative Parser where 
pure v = P (\str -> [(v, str)]) 

(P g) <*> (P f) = P (\str -> [(g' v, s) | (g',s) <- g str, (v,_) <- f str])

(P g) <*> (P f) = P (\str -> f str >>= \(v,s1) -> g s1 >>= \(g',s2) -> [(g' v,s2)]) 

（10X非常多的@Will内斯对<*>助人）

因此...下面

*Main> parse (P (\s -> [((+3), s)]) <*> pure 2) "test" 
[(5,"test")] 

*Main> parse (P (\s -> [((,), s ++ " altered")]) <*> pure 2 <*> pure 4) "test" 
[((2,4),"test altered")] 

Answer 6

有些人做了伟大的工作上“分步”指南您可以轻松了解计算进度以创建最终结果。所以我不会在这里复制它。

我认为，你真的需要深入了解Functor和Applicative Functor。一旦你理解了这些话题，其他人就会像一二三（我的意思是大多数^^）一样容易。

所以：Functor，Applicative Functor及其应用在你的问题中是什么？

这些最好的教程：

• 的第11章 “了解你的一大利好哈斯克尔”：http://learnyouahaskell.com/functors-applicative-functors-and-monoids。

• 更多视觉“图片中的函子，应用程序和Monad”：http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html。

首先，当你想到函子，适用函子，想想“值上下文”：价值观是重要的，而计算环境也很重要。你必须处理他们两个。

类型的定义：

-- 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是包裹在P数据构造的功能。所以如果你得到一个值b :: Parser Char，并且你想将它应用到某些输入中，你必须打开b中的内部函数。这就是为什么我们有函数parse，它展开内部函数并将其应用于输入值。

而且，如果要创建Parser值，则必须使用P数据构造函数环绕一个函数。

二，函子：东西可以被“映射”过来，功能FMAP规定：

fmap :: (a -> b) -> f a -> f b 

我经常调用的函数g :: (a -> b)是正常功能，因为当你看到没有上下文环绕它。因此，为了能够将g应用于f a，我们必须以某种方式从f a中提取a，以便g可以单独应用于a。这种“莫名其妙”要看具体的函子，是你工作的背景：

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

• g是(a -> b)类型的功能，p是f a类型。

• 若要解开p，要获取上下文的值，我们必须通过一些输入值：parse p inp，然后该值是元组的第一个元素。将g应用于该值，得到类型为b的值。

• 的fmap结果是f b类型的，所以我们必须包装全部产生相同的背景下，为什么我们有：fmap g p = P (\inp -> ...)。

在这个时候，你可能会想知道，你可以有fmap的实施方式，其中的结果，而不是[(g v, out)]，是[(g v, inp)]。答案是肯定的。你可以用你喜欢的任何方式实现fmap，但重要的是成为一个合适的函子，实施必须遵守函数法。法律是我们推导这些功能实现的方式（http://mvanier.livejournal.com/4586.html）。执行必须至少满足2个Functor法则：

• fmap id = id。
• fmap (f . g) = fmap f . fmap g。

fmap通常写为中缀运算符：<$>。当你看到这个时，看第二个操作数来确定你正在使用哪个Functor。

三，适用函子：你申请一个包裹函数来包裹值来获得另一个包裹值：

<*> :: f (a -> b) -> f a -> f b 

• 展开内部功能。
• 展开第一个值。
• 应用函数并包装结果。

你的情况：

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) 

• pg是f (a -> b)类型，px是f a类型。
• 解开g从pg由parse pg inp,g是元组的第一个。
• 展开px并将g应用于fmap g px。 注意，结果函数仅适用于out，在某些情况下，即"bc"而不是​​。
• 结果全：P (\inp -> ...)。

与Functor一样，Applicative Functor的实现必须遵守Applicative Functor定律（在上面的教程中）。

四，适用于您的问题：通过传递​​它

parse (pure (\x y -> (x,y)) <*> item <*> item) "abc" 
      |   f1  | |f2|  |f3| 

• 展开f1 <*> f2：通过传递​​它
  • 展开f1，我们得到[(g, "abc")]。
  • 然后fmapg上f2并通过out="abc"它：
    • 展开f2得到[('a', "bc")]。
    • 应用g对'a'得到一个结果：[(\y -> ('a', y), "bc")]。
• 然后fmap第1个要素上f3的结果的并通过out="bc"它：
  • 展开f3得到[('b', "c")]。
  • 应用'b'的功能得到最终结果：[(('a', 'b'), "c")]。

总之：

• 需要一段时间的想法， “假摔” 到你。特别是，这些法则推导出实现。
• 下一次，设计您的数据结构以便于理解。
• Haskell是我最喜欢的语言之一，我很快就会成为你的，所以要耐心等待，它需要一个学习曲线，然后你走！

快乐哈斯克尔黑客！