7 import Control.Applicative
11 -- A parser for a value of type a is a function which takes a String
12 -- represnting the input to be parsed, and succeeds or fails; if it
13 -- succeeds, it returns the parsed value along with the remainder of
15 newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }
17 -- For example, 'satisfy' takes a predicate on Char, and constructs a
18 -- parser which succeeds only if it sees a Char that satisfies the
19 -- predicate (which it then returns). If it encounters a Char that
20 -- does not satisfy the predicate (or an empty input), it fails.
21 satisfy :: (Char -> Bool) -> Parser Char
24 f [] = Nothing -- fail on the empty input
25 f (x:xs) -- check if x satisfies the predicate
26 -- if so, return x along with the remainder
27 -- of the input (that is, xs)
29 | otherwise = Nothing -- otherwise, fail
31 -- Using satisfy, we can define the parser 'char c' which expects to
32 -- see exactly the character c, and fails otherwise.
33 char :: Char -> Parser Char
34 char c = satisfy (== c)
38 *Parser> runParser (satisfy isUpper) "ABC"
40 *Parser> runParser (satisfy isUpper) "abc"
42 *Parser> runParser (char 'x') "xyz"
47 -- For convenience, we've also provided a parser for positive
49 posInt :: Parser Integer
54 | otherwise = Just (read ns, rest)
55 where (ns, rest) = span isDigit xs
57 ------------------------------------------------------------
58 -- Your code goes below here
59 ------------------------------------------------------------
61 -- Exercise 1. functor instance for Parser
62 instance Functor Parser where
63 -- Parser a == String -> (a, String)
64 -- first :: (a -> b) -> (a, c) -> (b, c)
65 -- fmap :: (a -> b) -> Parser a -> Parser b
66 fmap f (Parser pf) = Parser (\s -> case (pf s) of
68 Just v -> Just $ (uncurry (first f) v))
69 where first f' a b = (f' a, b)
71 -- Exercise 2. Applicative instance of Parser
72 instance Applicative Parser where
73 -- pure :: a -> Parser a
74 pure x = Parser (\inp -> Just (x, inp))
75 -- -- (<*>) :: Parser (a -> b) -> Parser a -> Parser b
76 -- -- Parser (a -> b) == String -> Maybe (a -> b, String)
77 -- -- Parser a == String -> Maybe (a, String)
78 -- one possible implementation.
79 (Parser pf) <*> (Parser p2) = Parser (\inp -> case (pf inp) of
81 Just (f, remStr) -> case (p2 remStr) of
83 Just (vp2, s) -> Just ((f vp2), s))
85 abParser :: Parser (Char, Char)
86 -- (,) :: a -> b -> (a,b)
87 -- char 'a' :: Parser Char
88 -- fmap f x :: (a -> b) -> f a -> f b
89 -- fmap (,) (char 'a') :: (Char -> (b -> (Char,b))) -> Parser Char -> Parser (b -> (Char, b))
90 -- so output if fmap (,) (char 'a') is of type --- Parser (b -> (Char, b))
91 -- now, p <*> char 'b' :: Parser (b -> (Char, b)) -> Parser Char -> Parser (Char, Char)
92 abParser = (,) <$> char 'a' <*> char 'b'
94 abParser_ :: Parser ()
95 abParser_ = (\_ _ -> ()) <$> char 'a' <*> char 'b'
97 intPair :: Parser [Integer]
98 intPair = (\x _ z -> x : z : []) <$> posInt <*> char ' ' <*> posInt
101 -- class Applicative f => Alternative f where
103 -- (<|>) :: f a -> f a -> f a
104 instance Alternative Parser where
105 empty = Parser(\_ -> Nothing)
106 (Parser p1) <|> (Parser p2) = Parser (\inp -> case (p1 inp) of
110 -- exercise 5: int or Uppercase
111 intOrUppercase :: Parser ()
112 intOrUppercase = ((\_ -> ()) <$> posInt) <|> ((\_ -> ()) <$> (satisfy isUpper))