I'm exploring FP / parser combinators in Rust, and trying to follow along based on some other examples I've seen in a tutorial in F#. I have the following code:

struct ParseError(String);

trait Parser<T>: Fn(&str) -> (Result<T, ParseError>, &str) {}

impl<T, F> Parser<T> for F where F: Fn(&str) -> (Result<T, ParseError>, &str) {}

fn or_else<T>(parser1: &impl Parser<T>, parser2: &impl Parser<T>) -> impl Parser<T> {
    move |input| {
        let (result1, remaining1) = parser1(input);

        match result1 {
            Ok(token1) => (Ok(token1), remaining1),
            Err(_) => parser2(remaining1),
        }
    }
}

fn choice<T>(parsers: &[&impl Parser<T>]) -> impl Parser<T> {
    move |input| {
        let parser = parsers
            .iter()
            .reduce(|parser1, parser2| &&or_else(*parser1, *parser2));

        parser.unwrap()(input)
    }
}

I defined Parser<T> the way it is because I don't believe there is any other way to have a type alias for a closure type like I have here; this seems to be the closest equivalent. If there is a more idiomatic way, it would be good to know. The parsers are passed by reference as I don't want the combinator to render the parsers passed to it unusable after they are composed (as they don't rely on other state).

My goal is to be able to take a collection of parsers and apply them in sequence until one passes. Building this (playground link), though, I get this error:

   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/lib.rs:22:40
   |
 7 | fn or_else<T>(parser1: &impl Parser<T>, parser2: &impl Parser<T>) -> impl Parser<T> {
   |                                                                      -------------- the found opaque type
...
18 | fn choice<T>(parsers: &[&impl Parser<T>]) -> impl Parser<T> {
   |                          -------------- expected this type parameter
...
22 |             .reduce(|parser1, parser2| &&or_else(*parser1, *parser2));
   |                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `impl Parser<T>`, found opaque type
   |
   = note: expected reference `&&impl Parser<T>` (type parameter `impl Parser<T>`)
              found reference `&&impl Parser<T>` (opaque type at <src/lib.rs:7:70>)
   = help: type parameters must be constrained to match other types
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` (lib) due to 1 previous error

I don't see where the mismatch is, and reading through the book doesn't really clarify to me how I'd go about solving this either. My current understanding is that as each return of or_else is an impl Parser<T>, an opaque type, each version of it is different and they can't be passed in as a parameter in further calls to or_else, which use impl Parser<T> in the parameter position, which expects a specific concrete type. However, I don't think my understanding is on the right track.

In all honesty, I'm not even sure I'm going about this idiomatically. How should I go about structuring this code to model what I stated above? How can I go about fixing this / what is the error actually saying?

2 posts - 2 participants

Read full topic