some minor beautifications
authorMiguel <m.i@gmx.at>
Tue, 19 Mar 2019 18:24:07 +0000 (19:24 +0100)
committerMiguel <m.i@gmx.at>
Tue, 19 Mar 2019 18:24:07 +0000 (19:24 +0100)
00_blog/00040_Haskell/00150_Applicative-vs-Monadic-Parsing/index.md

index 800bab3..e57e084 100644 (file)
@@ -90,17 +90,14 @@ instance Monad (Parser a) where
     where g inp = case parse p inp of Just (a,b) -> parse (f a) b
                                       _          -> Nothing
 
-parse :: Parser a b -> a -> Maybe (b,a)
-parse (Parser f) inp = f inp
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ## Primitives
 
 We also need at least a minimal set of primitives to parse something.
 Note that the primitives can give you the effects of Applicative or 
-Alternative even if there's no instance (as dmwit pointed out on #haskell).
-E.g. the _word_ primitive below, could not be composed, by combining the
-_char_ parsers in an applicative style only.
+Alternative even if the Parser itself is not an instance of these.
+(Thanks to dmwit for pointing this out on #haskell).
 
 The _num_ parser makes use of the _some_ combinator which requires our
 Parser to be an instance of _Alternative_ as well. _Applicative_ 
@@ -108,11 +105,6 @@ alone is of limited use in practice since without it, we also lack
 the <|> combinator.
 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ {.haskell .numberLines}
-word :: String -> Parser String String
-word w = Parser g where l     = length w
-                        g inp = if take l inp == w then Just (w,drop l inp) 
-                                                   else Nothing
-
 satisfy :: (Char -> Bool) -> Parser String Char
 satisfy f = Parser g  where g (x:xs) | f x = Just (x,xs)
                             g _            = Nothing
@@ -128,13 +120,23 @@ notChar c = satisfy (/=c)
 
 num :: Parser String Int
 num = read <$> some (satisfy isDigit) 
+
+word :: String -> Parser String String
+word (c:cs) = (:) <$> char c <*> word cs
+word _ = pure ""
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 ## Applicative / Alternative parsing
 
+Now we are able to parse any context free grammar, given our 
+_satisfy_ Parser along with Applicative, Alternative, and recursion.
+
 Let's parse something! 
 
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ {.haskell .numberLines}
+-- we parse, by simply applying the function encapsulated in our Parser on the input.
+parse (Parser f) inp = f inp
+
 -- well-formed parentheses are the canonical example of a context-free grammar
 parsePar = concat <$> some parseP where parseP = word "()" <|> (char '(' *> parsePar <* char ')')
 parse parsePar "((()())()())"
@@ -180,3 +182,4 @@ As usual, use the simplest tool that will suffice :smile:
 * <http://dev.stephendiehl.com/fun/002_parsers.html>
 * <https://eli.thegreenplace.net/2017/deciphering-haskells-applicative-and-monadic-parsers/>
 * <https://byorgey.wordpress.com/2012/01/05/parsing-context-sensitive-languages-with-applicative/>
+* <https://arunraghavan.net/2018/02/applicative-functors-for-fun-and-parsing/>