Creating a HashMap with a function with reference paramaters as key

Question

I'm trying to create a HashMap where the key type is a function with a reference paramater. let mut hm: HashMap<fn(&u32) -> u32, u32> = HashMap::new();. This works fine, but i cant insert anything into the map. The compiler says it's not legal since trait bounds weren't satisfied

rules.insert(
  |v: &u32| v + 1,
  0,
);

gives

the method `insert` exists but the following trait bounds were not satisfied:
           `for<'r> fn(&'r u32) -> u32: Eq`
           `for<'r> fn(&'r u32) -> u32: Hash`

I've read about Lifetimes in the various texts, but i can't figure out how to solve this.

Background: I'm implementing wave function collapse. I want my implementation to be generic in the sense that any "grid" can be used, 1d, 2d, 3d, nd, hexagonal etc. To do this i use a "ruleset" which is a hashmap where the key is a function that takes a cell coordinate and returns its neighbours, and the value is the rule for how to collapse said neighbours' states. The key function takes an index and a reference to the "grid" and returns the index of the neihbour.

Answer 1

If you want to support multiple grid implementations, the most natural approach is to define a Grid trait that abstracts differences between the grids. Here's one I made up, loosely based on your use case description:

enum CollapseRule {
    A,
    B,
}

trait Grid {
    const COLLAPSE_RULE: CollapseRule;

    fn neighbours(&self, index: usize) -> Vec<usize>;
}

#[derive(Clone, Debug, Default)]
struct Grid1d {
    vertices: Vec<f64>,
}

impl Grid for Grid1d {
    const COLLAPSE_RULE: CollapseRule = CollapseRule::A;

    fn neighbours(&self, index: usize) -> Vec<usize> {
        let len = self.vertices.len();
        match index {
            0 => vec![1],
            _ if index < len => vec![index - 1, index + 1],
            _ if index == len => vec![index - 1],
            _ => panic!(),
        }
    }
}

Whereever your code needs to accept a grid, you can accept a generic type G with a trait bound G: Grid, and any interaction with the grid happens via the trait. Your trait will likely need more functions than in my simplistic example.

Answer 2

The immediate issue you're running into is that Rust's HashMap requires its keys to be Hash and Eq, and the closure you provide does not implement either trait. Function pointers (fn(T, U) -> V) are Hash and Eq, but less flexible than closures.

Even if closures could implement Hash and Eq, you couldn't make them useful as HashMap keys. From the Rust reference, §10.1.12:

A closure expression produces a closure value with a unique, anonymous type that cannot be written out. [emphasis added]

In other words, no two closures can have the same type, even if their contents are identical! As a result, the types of any two closures you attempt to add as keys will conflict.

---

I'm not too familiar with wave function collapse (which you mention in your comment), but a solution here could be to use some type that describes the function as the key, rather than the function itself. Take this very simple example:

#[derive(PartialEq, Eq, Hash)]
pub struct KeyFunction {
    to_add: i32,
}

impl KeyFunction {
    pub fn apply(&self, param: &i32) -> i32 {
        *param + self.to_add
    }
}

type Ruleset<V> = HashMap<KeyFunction, V>;

This will limit the keys you can use in a particular ruleset based on what information the KeyFunction type stores. However, you could use a trait to genericize over different kinds of key function (playground link):

use std::collections::HashMap;

pub trait KeyFunction {
    type Coord;

    fn apply(&self, input: &Self::Coord) -> Self::Coord;
}

/// Descriptor type for simple, contextless 2-D key functions.
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct D2KeyFunction {
    x_ofs: i32,
    y_ofs: i32,
}

impl KeyFunction for D2KeyFunction {
    type Coord = (i32, i32);

    fn apply(&self, input: &Self::Coord) -> Self::Coord {
        (input.0 + self.x_ofs, input.1 + self.y_ofs)
    }
}

type D2Ruleset<V> = HashMap<D2KeyFunction, V>;

This allows you to have flexible key functions while working within Rust's type system, and also enforces boundaries between incompatible key functions.