4

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?
Peter Hall
  • 53,120
  • 14
  • 139
  • 204
max
  • 1,048
  • 10
  • 20
  • I have thought about this a bit, and it does seem a bit strange. I'm not sure if it's a bug or a limitation, but you have a workaround, so not too bad. I don't think there's any harm in reporting a bug to the Rust project - if it's not a bug, you will at least get a good explanation of what is going on! – Peter Hall Jan 19 '20 at 20:37
  • 1
    As an aside, you don't need the `for<'a>` annotations: the `Fn*` pseudo-traits already desugar to that. – Peter Hall Jan 19 '20 at 20:39
  • @PeterHall Thanks for your feedback. I tried removing the `for<'a>` annotations, but I get an `undeclared lifetime` error. Actually I don't think I can skip the annotation for rank-2 types (inference is undecidable), but maybe I'm missing something? – max Jan 19 '20 at 21:14
  • 1
    @max You need to remove all mentions of the lifetime as well. It basically behaves like lifetime elision in function signatures. The constraint simply becomes `F: Fn(&str) -> ParseResult`. – Sven Marnach Jan 19 '20 at 21:23
  • @SvenMarnach I see, thanks! – max Jan 19 '20 at 21:26
  • 1
    This is a type inference problem. You can't specify the type of a closure, so it's always inferred by the compiler. The inference happens based on the context the closure appears in, but it won't take into account the trait bound on the `Parser` impl. Your cast function does not need the explicit return type – just `F` as the return type will do. The important part of that function is that it constrains the closure, so the type inference engine has enough information to infer the right type. – Sven Marnach Jan 19 '20 at 21:27
  • See also https://stackoverflow.com/questions/58773989/why-does-this-simple-closure-fail-while-the-other-two-functions-succeed – Sven Marnach Jan 19 '20 at 21:30
  • 1
    This is very similar to [this bug on the Rust repo](https://github.com/rust-lang/rust/issues/41078), though there is an additional complication here due to the parametrized return type. – Sven Marnach Jan 19 '20 at 21:32

0 Answers0