Eat and peek could be pitched whenever. I wonder if we should do a closure-based (Character) -> Bool seek now, or invest more effort in a Pattern type. Find/replace/split is in a similar boat, and we want a Pattern that's useful for regexes, pegs, parser-combinators, etc.
Rust's str::Pattern seems like a good start. I don't think we'd limit it to Strings, rather have it for all Collections. This would (I think) be distinct from the protocol used for destructuring value-binding-patterns.