Can I implement a trait while capturing the environment?

Question

I'm trying to implement A* search for Advent of Code 2019 (Yes, Slowpoke, I know). I've started like this:

fn find_path(start: Coords, goal: Coords, map: &Vec<Vec<char>>) -> Vec<Coords> {        
    struct Node {
        distance: u32,
        pos: Coords,
    }
    impl PartialEq for Node {
        fn eq(&self, other: &Self) -> bool {
            self.distance + manhattan(self.pos, goal) == other.distance + manhattan(other.pos, goal)
        }
    }
    ...
    let mut edge = BinaryHeap::new();        
    edge.push(Node{distance: 0, pos: start});
    ...

Coords is a struct with an x and an y. The problem here is that I can't use goal in the trait, because it's not in scope. A closure would be able to capture it, but I am doubtful whether I can use a closure instead of a fn here. If so, what's the syntax? If not, is there a fundamental reason why it can't be done? I wasn't able to find an answer online.

I know the simple solution is to include goal in Node, but it's redundant because I'll be creating thousands of Node during A*, all of which will have the same goal, wasting memory and CPU cycles. In principle, goal could be a single global variable, but that's an untidy option.

Even though I'm sure including goal in Node would work fine in practice, I'd rather not.

Is there another idiomatic way of accomplishing what I'm trying to do?

[Why is it discouraged to accept a reference to a String (&String), Vec (&Vec), or Box (&Box) as a function argument?](https://stackoverflow.com/q/40006219/155423) — Shepmaster, Mar 01 '20 at 19:55

Shepmaster · Accepted Answer · 2020-03-01T20:04:16.860

No, you cannot capture any environment in an impl block. Closures capture the environment, so you cannot use a closure as a function in an impl block.

Functions and methods are designed to be called from any context, so there's no guarantee that there even is an environment to be captured. The fact that we can declare types, functions, methods, etc. inside of another function is basically a syntax nicety.

I'd probably create a type that wraps Node and goal:

struct Foo(Node, Coord);

impl Foo {
    fn value(&self) -> WhateverType {
        self.0.distance + manhattan(self.0.pos, self.1)
    }
}

impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool {
         self.value() == other.value()
    }
}

See also:

Thanks for the links. `petgraph` seems useful and I'll keep it in mind, although I wanted to create an A* implementation that didn't require me to explicitly enumerate all nodes from the outset. I have a grid map, the nodes are implicit. — Kristoffer Sjöö, Mar 02 '20 at 18:44

score 0 · Answer 2 · answered Mar 03 '20 at 08:03

The reason why I need PartialEq is that the Nodes are subsequently going into a BinaryHeap. If the BinaryHeap had an option to provide a custom comparator, that would be perfect: I wouldn't need Node to be Ord, and I could let goal reside in that comparator (closure).

It seems this is being considered: https://github.com/rust-lang/rust/pull/69454

In the meantime, there's a crate that provides that functionality: https://crates.io/crates/binary-heap-plus

For now, I'm going to accept the overhead of goal inside Node but it's good to know my options.

Can I implement a trait while capturing the environment?

2 Answers2