Core.hs

module ParseLib.Simple.Core
  (
    -- * The type of parsers
    Parser,
    -- * Elementary parsers
    anySymbol,
    satisfy,
    empty, failp,
    succeed, pure,
    -- * Parser combinators 
    (<|>),
    (<<|>),
    (<*>),
    (<$>),
    (>>=),
    -- * Lookahead
    look,
    -- * Running parsers
    parse
  )
  where

import Prelude hiding ((>>=))

-- | An input string is mapped to a list of successful parses.
-- For each succesful parse, we return the result of type 'r',
-- and the remaining input string. The input must be a list of
-- symbols.
type Parser s r  =  [s] -> [(r,[s])]

-- | Parses any single symbol.
anySymbol :: Parser s s
anySymbol (x:xs)  =  [(x,xs)]
anySymbol []      =  []

-- | Takes a predicate and returns a parser that parses a
-- single symbol satisfying that predicate.
satisfy  ::  (s -> Bool) -> Parser s s
satisfy p (x:xs) | p x       =  [(x,xs)]
satisfy _ _                  =  []

-- | Parser for the empty language, i.e., parser that always fails.
empty :: Parser s a
empty xs  =  []

-- | Same as 'empty'; provided for compatibility with the lecture notes.
failp :: Parser s a
failp = empty

-- | Parser that always succeeds, i.e., for epsilon.
succeed :: a -> Parser s a
succeed r xs = [(r,xs)]

-- | Same as 'succeed'; provided for compatiblity with the applicative
-- interface.
pure :: a -> Parser s a
pure = succeed

infixl 4  <$>, <*>
infixr 3  <|>, <<|>
infixl 1  >>=

-- | Choice between two parsers with the same result type.
(<|>) :: Parser s a -> Parser s a -> Parser s a
(p <|> q) xs  =  p xs ++ q xs

-- | Biased choice. If the left hand side parser succeeds,
-- the right hand side is not considered. Use with care!
(p <<|> q) xs  =  let r = p xs in if null r then q xs else r

-- | Sequence of two parsers.
(<*>) :: Parser s (b -> a) -> Parser s b -> Parser s a
(p <*> q) xs  =  [(f x,zs)
                 |(f  ,ys) <- p xs
                 ,(  x,zs) <- q ys
                 ]

-- | Map a function over the results of a parser. The '<$>' combinator
-- can also be defined in terms of 'succeed' and '<*>':
--
-- > f <$> p  =  succeed f <*> p
--
(<$>) :: (a -> b) -> Parser s a -> Parser s b
(f <$> p) xs  =  [(f y,ys)
                 |(  y,ys) <- p xs
                 ]

-- | Monadic bind. Do not use this combinator unless absolutely
-- required. Most sequencing can be done with '<*>'.
(>>=) :: Parser s a -> (a -> Parser s b) -> Parser s b
(p >>= f) xs  =  [(z  ,zs)
                 |(y  ,ys) <- p xs
                 ,(z  ,zs) <- f y ys
                 ]

-- | Returns the rest of the input without consuming anything.
look :: Parser s [s]
look xs = [(xs, xs)]

-- | For compatibility with the "newtype" version of the library:
-- runs a parser on a given string.
parse :: Parser s a -> [s] -> [(a, [s])]
parse = id