import Monad
import Char

-- >>= je neefektivni, ale da se (temer) odstranit:
-- mzero >>= _ = mzero
-- (a `mplus` b) >>= f = (a >>= f) `mplus` (b >>= f)
-- return x >>= f = f x

-- co se symbol a eof?
-- reseni -- zavedeme SymbolBind a EofBind:
-- SymbolBind f = symbol >>= f
-- EofBind p = eof >> p

data P s a = SymbolBind (s->P s a)
             | EofBind (P s a)
             | Fail
             | P s a :++ P s a
             | Return a

onEof x = EofBind (Return x)
symbol = SymbolBind Return

instance Monad (P s) where
  SymbolBind fs >>= f = SymbolBind (\s -> (fs s >>= f))
  EofBind p >>= f = EofBind (p >>= f)
  Fail >>= _ = Fail
  (p :++ q) >>= f = (p >>= f) :++ (q >>= f)
  Return x >>= f = f x
  return x = Return x

instance MonadPlus (P s) where
  mplus a b = a :++ b
  mzero = Fail

parse::P s a -> [s]->[(a,[s])]
parse (SymbolBind f) [] = []
parse (SymbolBind f) (c:s) = parse (f c) s
parse (EofBind p) [] = parse p []
parse (EofBind _) (_:_) = []
parse Fail _ = []
parse (p :++ q) s = parse p s ++ parse q s
parse (Return x) s = [(x,s)]

-- odstranena tvorba pomocnych seznamu v :>>=
-- ale cas i pamet vyjdou mnohem horsi...
-- (13.59 secs, 755 755 248 bytes) pro test s replicate 1000