import Monad
import Char

-- zbavme :++ (odstrani se pouziti ++)
-- Return nahradime ReturnPlus
-- ReturnPlus x p = Return x :++ p
-- spojime SymbolBind a EofBind
-- [SEofBind fs pe] [] = [pe] []
-- [SEofBind fs pe] (c:s) = [fs c] s

data P s a = SEofBind (s->P s a) (P s a)
             | Fail
             | ReturnPlus a (P s a)

onEof x = SEofBind (\_->Fail) (return x)
symbol = SEofBind return s Fail

instance Monad (P s) where
  SEofBind fs pe >>= f = SEofBind (\s -> (fs s >>= f)) (pe >>= f)
  Fail >>= _ = Fail
  ReturnPlus x p >>= f = f x `mplus` (p >>= f)
  return x = ReturnPlus x Fail

instance MonadPlus (P s) where
  mplus Fail a = a
  mplus a Fail = a
  mplus (ReturnPlus x p) q = ReturnPlus x (p `mplus` q)
  mplus p (ReturnPlus x q) = ReturnPlus x (p `mplus` q)
  mplus (SEofBind f fe) (SEofBind g ge) = SEofBind (\c -> f c `mplus` g c) (fe `mplus` ge)
  mzero = Fail

parse::P s a -> [s]->[(a,[s])]
parse (SEofBind _ e) [] = parse e []
parse (SEofBind f _) (c:s) = parse (f c) s
parse Fail _ = []
parse (ReturnPlus x p) s = (x,s) : parse p s

-- cas i pamet stale dost strasne
-- (4.90 secs, 548 446 228 bytes) pro test s replicate 1000