chainl1を申請者を使って表現することは可能ですか？

Question

parsecによって定義されたMonadインスタンスを使わずに、chainl1コンビネータをParsecから表現することはできますか？

chainl1 p op = 
    do x <- p 
    rest x 
    where 
    rest x = do f <- op 
       y <- p 
       rest (f x y) 
      <|> return x 

Answer 1

はい、それは次のとおりです。

chainl1 p op = foldl (flip ($)) <$> p <*> many (flip <$> op <*> p) 

アイデアは、あなたがp (op p)*を解析し、(...(((p) op p) op p)...)としてそれを評価しなければならないということです。

それは定義を少し拡大に役立つかもしれない：

chainl1 p op = foldl (\x f -> f x) <$> p <*> many ((\f y -> flip f y) <$> op <*> p) 

opとpのペアが解析されるように、結果がすぐに適用されますが、pはopの右オペランドであるので、それはA必要flip。

したがって、many (flip <$> op <*> p)の結果タイプはf [a -> a]です。この関数リストは、pという初期値で、左から右に、foldlで適用されます。 Applicative

Answer 2

醜い同等の定義：

chainl1 p op = 
    p <**> 
    rest 
    where 
    rest = flip <$> op <*> 
      p <**> 
      pure (.) <*> rest 
     <|> pure id 

の代わりに明示的に右側opに左側の引数xの通過、このApplicativeのフォーム「チェーン」op年代には、部分的に彼らの右に適用されます（したがってflip <$> op <*> p）を持ち上げコンビネータ(.)を介して受信し、rest :: Alternative f => f (a -> a)に最も左のpを(<**>)で適用します。