I'm starting to learn Rust (apologies in advance) and I'm trying to implement a monadic parser combinator library. Parsers implement a Parser
trait as follows:
// parse success is a value + the rest of input
type ParseResult<'a, T> = Option<(T, &'a str)>;
trait Parser<A> {
fn parse<'a>(&self, input: &'a str) -> ParseResult<'a, A>;
}
That is: the parse
method is lifetime-polymorphic. This trait can be implemented for lifetime-polymorphic functions/closures using Higher-Rank Trait Bounds as follows:
// parser impl for functions
impl<F, A> Parser<A> for F
where
for<'a> F: Fn(&'a str) -> ParseResult<'a, A>,
{
fn parse<'a>(&self, input: &'a str) -> ParseResult<'a, A> {
self(input)
}
}
My problem is that closures don't automatically satisfy the Parser
trait. Instead, it seems the type-checker needs some help from the programmer:
// higher-rank helper
fn cast<A, F>(func: F) -> impl Parser<A>
where
F: for<'a> Fn(&'a str) -> ParseResult<'a, A>,
{
func
}
// applicative pure parser
fn pure<A: Copy>(a: A) -> impl Parser<A> {
// doesn't work without explicit cast
cast(move |input| Some((a, input)))
}
Without the explicit cast, the error is:
error[E0271]: type mismatch resolving `for<'a> <[closure@src/lib.rs:29:5: 29:34 a:_] as std::ops::FnOnce<(&'a str,)>>::Output == std::option::Option<(A, &'a str)>`
--> src/lib.rs:27:27
|
27 | fn pure<A: Copy>(a: A) -> impl Parser<A> {
| ^^^^^^^^^^^^^^ expected bound lifetime parameter 'a, found concrete lifetime
|
= note: required because of the requirements on the impl of `Parser<A>` for `[closure@src/lib.rs:29:5: 29:34 a:_]`
= note: the return type of a function must have a statically known size
My questions are the following:
- Is this behavior normal? (i.e. the fact that the closure type remains lifetime-monomorphic when checking the
Parser
trait without explicit coercion) - Is there a better/more idiomatic way of making closures satisfy the
Parser
trait? - Or is this approach completely wrong and what would be the rusty way?