0

I'm writing a priority queue, and I want to allow a custom comparator, but also provide a default option.

pub struct PriorityQueue<T: PartialOrd, F: Fn(&T, &T) -> bool> {
    heap: Vec<T>,
    compare: F,
}

impl<T: PartialOrd, F: Fn(&T, &T) -> bool> PriorityQueue<T, F> {
    pub fn new(data: Vec<T>) -> Self {
        Self::with_ordering(data, |a, b| a < b)
    }

    pub fn with_ordering(data: Vec<T>, ordering: F) -> Self {
        let mut queue = Self {
            heap: data,
            compare: ordering,
        };
        queue.heapify();
        queue
    }
}

Rust doesn't like this though:

error[E0308]: mismatched types
 --> src/lib.rs:8:35
  |
6 | impl<T: PartialOrd, F: Fn(&T, &T) -> bool> PriorityQueue<T, F> {
  |                     - this type parameter
7 |     pub fn new(data: Vec<T>) -> Self {
8 |         Self::with_ordering(data, |a, b| a < b)
  |                                   ^^^^^^^^^^^^ expected type parameter `F`, found closure
  |
  = note: expected type parameter `F`
                    found closure `[closure@src/lib.rs:8:35: 8:47]`
  = help: every closure has a distinct type and so could not always match the caller-chosen type of parameter `F`

For more information about this error, try `rustc --explain E0308`.

This error makes sense, but I don't really know how to work around it. My first thought was to create a second impl block where I specified that F is the type of |a, b| a < b, but I don't know what syntax I could use to specify that. What can I do here?

Michael Dorst
  • 8,210
  • 11
  • 44
  • 71
  • I tried to give an answer but I was too slow, I'm sorry. So I'll post it here – Finomnis Jul 07 '22 at 09:25
  • You make the type `F` a generic, but then you fix its type to the closure in the constructor. This in itself is a contradiction. I don't think you can have functions for structs that themselves define the template type, because the type has to be known **before** you call the function. The way to solve this is to completely remove the `F` generic and instead use a `Box` for storing the closure: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=96d850d9af94b29c14a1cd9da54d5358 – Finomnis Jul 07 '22 at 09:25
  • To understand in more detail why the concept of setting the type of a generic in your own constructor is impossible, you should read the duplicate question. – Finomnis Jul 07 '22 at 09:33
  • As an immediate workaround you can move the `new` function into it's own `impl` block where F is substituted with fn pointer: `impl PriorityQueue bool> { pub fn new(data: Vec) -> Self { Self::with_ordering(data, |a, b| a < b) } }` – Dawer Jul 07 '22 at 10:21

0 Answers0