Created
June 30, 2014 00:39
Revisions
-
avalonalex created this gist
Jun 30, 2014 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,55 @@ {-# OPTIONS -Wall -fwarn-tabs -fno-warn-type-defaults #-} -- The basic definition of the parsing monad. module Parser (Parser, get, choose, (<|>), satisfy, doParse, ) where newtype Parser a b = P ([a] -> [(b, [a])]) doParse :: Parser a b -> [a] -> [(b, [a])] doParse (P p) s = p s -- | Return the next character get :: Parser a a get = P (\cs -> case cs of (x:xs) -> [ (x,xs) ] [] -> []) -- | Return the next character if it satisfies the given predicate satisfy :: (a -> Bool) -> Parser a a satisfy p = do c <- get if (p c) then return c else fail "End of input" instance Monad (Parser a) where -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b p1 >>= fp2 = P (\cs -> do (a,cs') <- doParse p1 cs doParse (fp2 a) cs') -- return :: a -> Parser a return x = P (\cs -> [ (x, cs) ]) -- fail :: String -> Parser a fail _ = P (\_ -> [ ] ) instance Functor (Parser a) where -- fmap = liftM fmap f p = do x <- p return (f x) -- | Combine two parsers together in parallel, producing all -- possible results from either parser. choose :: Parser a b -> Parser a b -> Parser a b p1 `choose` p2 = P (\cs -> doParse p1 cs ++ doParse p2 cs) -- | Combine two parsers together in parallel, but only use the -- first result. This means that the second parser is used only -- if the first parser completely fails. (<|>) :: Parser a b -> Parser a b -> Parser a b p1 <|> p2 = P $ \cs -> case doParse (p1 `choose` p2) cs of [] -> [] x:_ -> [x]