module ParseLib where
import Char

type Parser t r = [t] -> [(r,[t])] 

epsilon :: Parser t Bool
epsilon xs = [(True, xs)]

term t = sat ((==)t)
termRes t r = term t << (\_ -> r)

sat pred [] = []
sat pred (x:xs)
 |pred x = [(x,xs)]
 |otherwise = []

(/|) :: Parser t r -> Parser t r -> Parser t r
(/|) p1 p2 xs = p1 xs ++ p2 xs

(/-) :: Parser t r1 -> Parser t r2 -> Parser t (r1,r2)
(/-) p1 p2 xs = [((r1,r2) , t2 ) | (r1,t1) <- p1 xs, (r2,t2) <- p2 t1 ]

rep0 p =    p /- rep0 p  << (\(x,xs) -> x:xs) 
         /| epsilon      << (\_ -> [])

rep1 p =  p /- rep0 p    << (\(x,xs) -> x:xs) 

(<<) :: Parser t r1 -> (r1 -> r2) -> Parser t r2
(<<) p f xs = [ (f r1, ts) |(r1,ts) <-p xs]

infixl 8 /-
infixl 6 <<
infixl 4 /|

isNum str = and [isDigit c|c<-str]

number :: Parser String Int
number = sat isNum << read

opList basis op 
  = basis /- (rep0 (op /- basis  << (\(f,n) -> \n1 -> f n1 n )) << foldl (.) id)
       << (\(n,f)->f n)

expr  = opList mexpr ( termRes "+" (+) /|termRes "-" (-) )
mexpr = opList atom  ( termRes "*" (*) /|termRes "/" div )

{--
expr = mexpr /-
             (rep0 (( term "+" << (\_ -> (+))
                   /|term "-" << (\_ -> (-)) ) 
                  /- mexpr  << (\(f,n) -> \n1 -> f n1 n )) << foldl (.) id)
          << (\(n,f)->f n)

mexpr = atom /-
             (rep0 (( term "*" << (\_ -> (*))
                   /|term "/" << (\_ -> div) ) 
                  /- atom  << (\(f,n) -> \n1 -> f n1 n )) << foldl (.) id)
          << (\(n,f)->f n) --}

atom =    number
       /| term "(" /- expr /- term ")" << (\((_,n),_)->n)