Skip to content

Instantly share code, notes, and snippets.

@avalonalex
Created June 30, 2014 00:39

Revisions

  1. avalonalex created this gist Jun 30, 2014.
    55 changes: 55 additions & 0 deletions ParserMonad.hs
    Original 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]