のApplicativeファンクタ：<*>と部分適用、私はグラハム・ハットンによってハスケル</em>で書籍<em>プログラミングを読んでいると私は<code><*></code>と部分アプリケーションが文字列を解析するために使用することができます方法を理解するためにいくつかの問題を抱えている

Question

それがどのように動作しますか。

私はpure (+1)がJust (+1)を生成し、その後Just (+1) <*> Just 2 がJust (2+1)生成し、その後Just 3

しかし、このような、より複雑な場合にはJust 3 のでpure (+1) <*> Just 2 が生成することを知っている：

-- 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)]) 

これで、1つのパラメータを持つパーサーが作成されました。その後

：

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)) - どの(,) - 入力文字列を解析することによって生成されたの出力値に適用されています。あなたの暫定パーサによって生成された値の順序は次のとおりです。等式推論での作業

-- 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' 

（可能であれば、入力Stringのヘッド外れ1 Charを取るitem手段と解析）そして、

-- 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 

（<*>入力を解析するために、第1の解析を使用して、新しい合成パーサを生成フィット結果のタイプを有する2つのパーサを組み合わせ、次いで結合、残りの文字列を解析するために、第2のパーサーを使用し新しい、結合されたパーサの結果を生成する2つの結果）。

さて、<*>仲間左へは、そうあなたが求めるものについて、右端<*>が最上位である

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)] 

同様に、ネストされた発現は

0123のように簡略化されます

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")] 

ので、私たちは、私は結果が[(((,) 'a') 'b', "c")]になりますなぜあなたが今見ることができると思い

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

を取得します。

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 item outを残しておきます）最初の2つのparse式を減らすことができます。

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の定義により

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

この

明らかに

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

に減少し、パターンが最初のケースでは一致していないが、彼らは、第二のケースで行います。 2番目の式のパターンにマッチを代入します。

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)] 

、第二のパターンが一致し、我々はあなたが二<*>アプリケーションを評価するために、この同じプロセスを適用した場合

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

---

に減少し、置換

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

を行います結果をparse（結果）に入れます​​exprあなたは、式が実際に[(('a','b'),"c")]に減少するのを見るでしょう。

Answer 3

これらのことを学ぶのに役立つものは、タイプのに焦点を当てることでした。これはすべて、値に関数を適用することです（または、関数をに2つの値に適用する場合）。

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

だからのFunctorと我々は（。。、すなわち、たぶんリスト）「コンテナ/コンテキスト」内の値に関数を適用し、Applicativeので私たちが適用する機能がありますそれ自体が「コンテナ/コンテキスト」内にある。

適用する関数は(,)であり、関数を適用する値はコンテナ/コンテキスト内にあります（ケースParser a）。私たちは同じ「コンテキスト/コンテナ」に機能(,)を持ち上げpureを使用して

は、私たちの価値観は、私たちが任意の Applicativeの（たぶん、リスト、パーサ、に関数を持ち上げるためにpureを使用することができ、ノート（です。 。）：

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

たちはParserコンテキスト内でもある値にParserコンテキスト内で、今ある機能(,)を適用することができ<*>を使用します。 +1で指定した例との1つの違いは、(,)が2つの引数を持つことです。したがって、私たちは二度<*>を使用する必要があります。

(<*>) :: 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 

[OK]を、この答えは長いIより得ました期待！まあ、助けてくれるといいなあたぶん、Typeclassopediaを見て、無限の美しいプロセスであるハスケルを学びながら、貴重なものを見つけました。 。 :)

Answer 4

まず、一つのことを強調したいと思います。私は、理解の要点は、Parserとパーサーをparseで実行していることに気づくことにあります。

パーサーを実行すると、Parserと入力文字列がparseになり、可能な解析のリストが表示されます。私はそれがおそらく理解しやすいだろうと思う。

parseParser（接着剤を使用して構築することができます）<*>に合格します。 parseにParser、a、またはParser,f <*> a <*> bを渡すと、同じタイプのもの、つまり(String -> [(a,String)])に相当するものが渡されることを理解してください。私はこれもおそらく理解しやすいと思うが、まだそれを "クリック"するのに時間がかかる。

私は、このアプライドグルーの性質について少し話します。<*>。適用例のF aは、タイプaのデータを生成する計算です。あなたは、このようないくつかのデータを返す一連の計算など

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

という用語と考えることができ、その後、 bその後、 c aを言います。 Parserの文脈では、計算は aを現在の文字列で探し、残りの文字列を gに渡します。計算/解析のいずれかが失敗した場合は、その全体が同様になります。

その

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

は私が個人的に発光のメンタルモデルを見つけ、任意の応用的にすべてのそれらの放出された値を収集するために最初に純粋な機能を書き込むことができますので、我々は一般的に書くことができることに注意することは興味深いです有用な収集。

だから、その長いプリアンブルは、実際の説明に。何ですか

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

do？さて、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

私はハスケルには経験はありませんが、とApplicativeParserタイプのインスタンスを生成しようとすると、次のようになります。したがって

(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)]) 

（<*>上@Willネスを助けるために非常に多くの10倍）

-- 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)]) 

...

*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について深く理解する必要があるということです。これらのトピックを理解すると、他のトピックは1つ2つの3つのものとして簡単になります（私はそれらのほとんどを意味します^^）。

だから：あなたの問題のFunctor、Applicative Functorとそのアプリケーションは何ですか？これらの

ベストチュートリアル：http://learnyouahaskell.com/functors-applicative-functors-and-monoids： "偉大な善のためにあなたにHaskellの学習" の

• 第11章。

• その他の視覚的な「画像の中のFunctor、Applicatives、Monads」：http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html。値が重要であり、計算コンテキストはあまりにも重要です：あなたはファンクタを考えるまず

、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の値が、リスト内のタプルの最初の要素です。

• ここでのコンテキストは、関数または最終的な値です。最終値を得るためには、入力を提供する必要があります。

ParserPデータコンストラクタに包まれた機能です。だから値b :: Parser Charがあり、それをある入力に適用したい場合は、bの内部関数をアンラップする必要があります。そのため、我々は関数parseを持っているので、内部関数をアンラップし、それを入力値に適用します。

そして、あなたはParser値を作成したい場合は、機能の周りPデータコンストラクタラップを使用する必要があります。

第二、ファンクタ：、オーバー「マッピング」機能によりFMAP指定することができる何か：あなたが見るようにするので、私は多くの場合、機能g :: (a -> b)を呼び出す

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

は通常機能ですそれを囲む文脈はありません。したがってgをf aに適用するには、aをf aから何らかの形で抽出する必要があります。gはaにのみ適用できます。それは「何とか」特定のFunctorに依存し、あなたが作業している状況である。

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

• gがpはタイプf aであり、タイプ(a -> b)の関数です。

• pをアンラップしてコンテキストの値を取得するには、入力値をparse p inpに渡す必要があります。値はタプルの最初の要素です。その値にgを入力し、bの値を取得します。なぜ我々は持っていることを、fmapの

• 結果はタイプf bであるので、我々は同じコンテキスト内のすべての結果をラップする必要があります：fmap g p = P (\inp -> ...)。このとき

、あなたは結果が、代わりに[(g v, out)]で、[(g v, inp)]であるfmapの実装を持っている可能性が疑問に思うかもしれません。答えは「はい」です。あなたは好きな方法でfmapを実装できますが、重要なことは適切なFunctorであることです。実装はFunctorの法律に従わなければなりません。法律は、それらの機能（http://mvanier.livejournal.com/4586.html）の実装を導き出す方法です。この実装は、少なくとも2つのファンクター法則を満たさなければならない。

• fmap id = id。
• fmap (f . g) = fmap f . fmap g。 <$>：

fmapは、多くの場合、中置演算子として書かれています。これを見ると、第2オペランドを見て、あなたが作業しているFunctorを特定します。第三に

、Applicativeのファンクタ：あなたは別のラップ値を取得するために包まれた値に包まれた機能を適用します。

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

• アンラップ内部機能。
• 第1の値をラップ解除します。
• 関数を適用し、結果をラップします。あなたのケースでは

：

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はpxはタイプf aであり、タイプf (a -> b)です。 parse pg inpによってpgから
• アンラップg、gはタプルの1です。
• pxを解除し、fmap g pxを使用して値にgを適用します。 注意の場合、結果関数はoutにのみ適用され、場合によっては"bc"ではなく​​に適用されます。
• 結果全体をラップします：P (\inp -> ...)。

Like Functor、Applicative Functorの実装は、Applicative Functorの法律（上記のチュートリアル）に従わなければなりません。

第四、あなたの問題に適用されます。

アンラップf1 <*> f2

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

• それに​​を渡すことによって：
  • アンラップf1それに​​を渡すことによって、私たちは[(g, "abc")]を取得します。
  • その後fmapf2上g、それにout="abc"を渡す：
    • アンラップf2[('a', "bc")]を取得します。
    • 'a'にgを入力すると、結果：[(\y -> ('a', y), "bc")]が得られます。 結果の
• その後fmap第一要素f3上、それにout="bc"を渡す：
  • アンラップf3[('b', "c")]を取得します。
  • 関数を'b'に適用して最終結果を得る：[(('a', 'b'), "c")]。
  結論で

：

• はあなたに "ダイブ" にアイデアをいくつかの時間を取ります。特に法律は実装を導き出している。
• 次回は、わかりやすいようにデータ構造を設計してください。
• ハスケルは私のお気に入りの言語の1つで、私はすぐにあなたのものになるので、忍耐強く、学習曲線が必要です。

ハッスルハッキング！