type Parser a = String -> [(a, String)]

result :: a -> Parser a
result v = \inp -> [(v, inp)]

zero :: a -> Parser a
zero v = \inp -> []

item :: Parser Char
item =
  \inp ->
    case inp of
      [] -> []
      (x:xs) -> [(x, xs)]

bind :: Parser a -> (a -> Parser b) -> Parser b
p `bind` f = \inp -> concat [f v inp' | (v, inp') <- p inp]

seq :: Parser a -> Parser b -> Parser (a, b)
p `seq` q = p `bind` \x -> q `bind` \y -> result (x, y)

sat :: (Char -> Bool) -> Parser Char
sat p =
  item `bind` \x ->
    if p x
      then result x
      else zero x

lower :: Parser Char
lower = sat (\x -> 'a' <= x && x <= 'z')