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.

Futnion pointers, FnOnce and FnMut, do not implement Eq nor Hash IIRC — Netwave
– Netwave, Commented Sep 29, 2021 at 15:25
@Netwave Function pointer totally do implement Eq and Hash as long as they are not generic, not even generic over a lifetime. FnOnce and FnMut of course don't, since they are not types. — Sven Marnach
– Sven Marnach, Commented Sep 29, 2021 at 15:38
What are you trying to achieve with this hash map? You can't use generic function parametrized by a lifetime as keys in a hash map. — Sven Marnach
– Sven Marnach, Commented Sep 29, 2021 at 15:41
I'd recommend instead storing an enum of all possible implementations and then matching on it to select the function to use instead. If the number of implementations isn't known at compile time, a boxed trait object could also be used, with some care on implementing Eq and Hash on dyn MyFnType. — Filipe Rodrigues
– Filipe Rodrigues, Commented Sep 29, 2021 at 18:20

Sven Marnach · Accepted Answer · 2021-09-29 19:44:23Z

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.

answered Sep 29, 2021 at 19:44

Sven Marnach

608k123 gold badges968 silver badges865 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lack of a better name Over a year ago

Thank you, this is also a great solution.

Mac O'Brien · Accepted Answer · 2021-09-29 18:22:21Z

0

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.

answered Sep 29, 2021 at 18:22

Mac O'Brien

2,95720 silver badges26 bronze badges

2 Comments

Lack of a better name Over a year ago

Thank you. This seems like a far better way of implementing it.

Sven Marnach Over a year ago

Closures that don't capture any variables coerce to function pointers, so they can be used as keys in a hash map. The problem with the closure in the question is that it is generic over a lifetime parameter, and generic function pointers do not implement Eq and Hash.

Collectives™ on Stack Overflow

Creating a HashMap with a function with reference paramaters as key

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related