{-|
Module      : Parsing
Description : Simple Monadic Parsing Library
Maintainer  : dave@chalmers.se

Used in the course Functional Programming GU/Chalmers

-}

module Parsing 
 ( Parser -- exports the type name but not the constructors
  ,parse  
  ,failure,sat,item,char,digit,
  (+++),
  oneOrMore,zeroOrMore,chain
 ) 

{----------------------

Aim: reusable Parser combinators including 
 a new type for the Parser, 
 but no export of the constructor

----------------------}
where

import Data.Char
import Data.Maybe

-- boilerplate for GHC 10.7 compatibility:
import Control.Applicative (Applicative(..))
import Control.Monad       (liftM, ap)
 
------------------

u = undefined -- for incomplete code
-- type Parser a = String -> Maybe (a,String)

-- | The abstract data type representing a Parser
data Parser a = P (String -> Maybe (a,String))

-- | Runs the parser on the given string 
--  to return maybe a thing and a string
parse :: Parser a -> String -> Maybe (a,String)
parse (P p) s = p s

------------------- 
-- | Parser than can never succeed
failure :: Parser a -- always fails
failure    = P $ \s -> Nothing
 
-- | Parser that succeeds without looking at the String
success :: a -> Parser a 
success a  = P $ \s -> Just (a,s)

-- | Parse any single character
item :: Parser Char
item  = P $ \s ->
         case s of 
              (c:s') -> Just (c,s')
              ""     -> Nothing

infixr 5 +++
-- | Try the first parser and if it fails try the second
(+++) :: Parser a -> Parser a -> Parser a
p +++ q  = P $ \s -> case parse p s of
                          Nothing -> parse q s
                          ok      -> ok
                          
              

-- (p >*> f) parse using p to produce x. 
-- Then parse using f x 

infixl 1 >*>

(>*>) :: Parser a -> (a -> Parser b) -> Parser b
p >*> f  = P $ \s -> 
             case parse p s of
                  Just(a,s') -> parse (f a) s'
                  _          -> Nothing
                  
-----------------------------------------------
-- Parsers below do not depend on the internal 
-- representation of Parser

-- | parse a single thing satisfying property p
sat :: (Char -> Bool) -> Parser Char
sat p  = do
       c <- item
       case p c of
             True -> success c
             False -> failure
                           

-- | parse a digit character
digit :: Parser Char
digit = sat isDigit

-- | Parse a specific character
char c = sat (== c)

-- example: parse any lowercase letter 
-- followed by its uppercase equivalent aA or bB etc.
ex1 = -- sat isAsciiLower >*> \c -> char (toUpper c)
   do c <- sat isAsciiLower
      char (toUpper c)


-- | Parse zero or more things 
zeroOrMore :: Parser a -> Parser [a]
zeroOrMore p = oneOrMore p +++ success []

-- | Parse one or more things 
oneOrMore :: Parser a -> Parser [a]
oneOrMore  p = do
                 a <- p
                 as <- zeroOrMore p
                 return (a:as)
                 

-- | Parse a list of as, separated by bs
chain :: Parser a -> Parser b -> Parser [a]
chain p q = do
      a <- p
      as <- zeroOrMore (q >> p)
      return $ a:as

-- example: comma separated digits "1,2,3"

-- Monad is a superclass of Applicative and Functor, but these
-- can always be defined as follows:
instance Functor Parser where
    fmap = liftM
instance Applicative Parser where
    pure  = return 
    (<*>) = ap
---------------------------------
-- This is the important part:

instance Monad Parser where
    (>>=)  = (>*>)   -- usually called "bind"
    return = success