It looks like modeling your parser as fn(str) -> (list-of (pair-of value remaining-str)) might work out as a more compact (in terms of code) and powerful representation. I did something similar when writing a combinator library for querying xml-like trees and it ended up quite powerful. (you can replace "str" with any sequence type).

For one thing, you can write parsers that return more than one value - i.e. parsers that are ambiguous about how they parse the string they are given. That lets you express "longest" and "shortest" as parser combinators rather than some special operation for each parser.