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

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是我最喜歡的語言之一，我很快就會成爲你的，所以要耐心等待，它需要一個學習曲線，然後你走！

快樂哈斯克爾黑客！