How does one create a struct that holds a type parameterized function in Rust?

Question

I am a beginner in Rust and am trying to create a Parser Combinator library in order to learn the ropes of the language. Very early on in this project I've gotten stuck. I want to have a Parser struct that holds the function used to parse data. Here is my attempt at implementing this.

struct Parser<I, O> {
    parse: impl Fn(&Vec<I>) -> Option<(&Vec<I>, O)>
}

Unfortunately, as the compiler informs me, i can not use the "impl Trait" notation in this way. Another way I've tried is by defining a separate type variable for the type of the function itself, as below.

struct Parser<I, O, F> 
where
    F: impl Fn(&Vec<I>) -> Option<(&Vec<I>, O)>
{
    parse: F
}

However, it seems redundant and unnecessary to have to provide the input, output, and function type, as the function type can be derived from the input and output. Also, the compiler gives me an error due to the fact that neither I or O are used.

I also considered Parser may have to be a trait rather than a struct. However I can't really wrap my head around what that would look like, and it seems like you would run into the same issue trying to define a struct that implemented the Parser trait.

Can you elaborate on how the parser is derived from the input and the output? — Chayim Friedman, Jul 14 '22 at 05:15
The parser takes a list of values (```&Vec```) and consumes some part of that input, returning a tuple of the remaining input, and whatever result the parser produced, wrapped in ```Option``` to represent the possibility of a parser failing. (```Option<(Vec, O)>```). For example, a parser made to parse the first 3 values of an input, when ran on ```[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]``` would return ```Some(([4, 5, 6, 7, 8, 9, 10], [1, 2, 3]))```. In that case ```I: i32``` and ```O: Vec```. The same parser when ran on the list ```[1, 2]``` would return ```None```. — Ben A., Jul 14 '22 at 05:20
But there could be another parser that too takes `I: i32` and `O: Vec`. The input/output can be derived from the parser, but not the opposite. — Chayim Friedman, Jul 14 '22 at 05:22
But wouldn't that parser have the same type as the one I described? I meant that the type of the Parser could be derived from ```I``` and ```O```, not necessarily the functionality. — Ben A., Jul 14 '22 at 05:24
No. I understand the point you don't understand now. If you want a uniform type, you need `fn()` or `Box`, not `impl Fn()`. Each function has a distinct type, but they can be converted to the uniform `fn` pointer. — Chayim Friedman, Jul 14 '22 at 05:26
Do you need your struct to be able to hold closures, or are simple functions enough? In the second case, you should use `parse: &fn (&Vec) -> Option<(&Vec, O)>` — Jmb, Jul 14 '22 at 05:34
@ChayimFriedman sorry, you're right it should be straight `parse: fn (&Vec) -> Option<(&Vec, O)>` — Jmb, Jul 14 '22 at 05:44
I need it to be able to hold closures, that way i can create functions that return parser with custom behavior. I've done some looking into it and I think the Box suggestion will work for me. Thank you. — Ben A., Jul 14 '22 at 05:49

score 1 · Accepted Answer · answered Jul 14 '22 at 11:54

Not a lot of context, but you I'll try doing it this way:

struct Parser<I, O> {
    parse: Box<dyn Fn(&Vec<I>) -> Option<(&Vec<I>, O)>>,
}

fn main() {
    let parser = Parser {
        parse: Box::new(|x| {
            Some((x, x.iter().sum::<i32>()))
        })
    };

    let v = vec![1, 2, 3, 4];
    let result = (parser.parse)(&v).unwrap();

    println!("{:?}", result);
}

For some more suggestion I would look here: How do I store a closure in a struct in Rust?

score 1 · Answer 2 · answered Jul 14 '22 at 18:43

I think all you need is std::marker::PhantomData to silence the error about unused generics. You can also make the code a bit more DRY with some type aliases. (I've replaced &Vec<I> with &[I] as the latter is a strict superset of the former.)

use std::marker::PhantomData;

type Input<'a,I> = &'a [I];
type Output<'a,I,O> = Option<(&'a [I], O)>;

struct Parser<I, O, F>
where
     F: Fn(Input<'_,I>) -> Output<'_, I, O>,
{
    parse: F,
    _phantom: PhantomData<(I, O)>,
}

impl<I, O, F> Parser<I, O, F>
where
    F: Fn(Input<'_, I>) -> Output<'_, I, O>,
{
    fn new(parse: F) -> Self {
        Self {
            parse,
            _phantom: PhantomData,
        }
    }

    fn parse_it<'a>(&'a self, input: Input<'a, I>) -> Output<'a, I, O> {
        (self.parse)(input)
    }
}

fn main() {
    let parser = Parser::new(|v: &[i32]| Some((v, v.iter().fold(0, |acc, x| acc + x))));
    println!("{:?}", parser.parse_it(&[1, 2, 3]));
    // ^ Some(([1, 2, 3], 6))
}

How does one create a struct that holds a type parameterized function in Rust?

2 Answers2