Crate recommendations for working with function types and adjunctions and trait-based impl specialization

help
1

Problem Setup

Many data structures such as BTreeMap<K, V> or Vector<T> etc. have a certain "map"-ness which I define as the function type Map<I, T> := I -> Option<T>.
We can think of such map types as representing formal sums

$ x = sum_(i in I) x(i) i $

and in fact, this sum representation is closer to how objects of this type are actually instantiated (e.g. using insert() or push()), where we omit all terms from the sum where x(i) == None.

Now given a function f :: I -> J there exists a natural contravariant map

conmap :: (I -> J) -> Map<J, T> -> Map<I, T>
conmap = flip (.)

which sends x as above to

$ x^f := sum_(i in I) x(f(i)) i $

or in Rust's lingo

fn conmap_get(orig_map: &Map<J, T>, f: &dyn Fn(I) -> J) -> &T {
    orig_map.get(f(key))
}

(disclaimer, I haven't tested this code).

There is also a natural covariant map

covmap :: (I -> J) -> Map<I, T> -> Map<J, T>

that sends x as above to

$ x_f = sum_(i in I) X(i) f(i) $

which (in the case of BTreeMap) would create a new owning map

let mut covmap_f_x = BTreeMap<J, T>::new();
for (key, val) in x.terms() {
    // let's pretend for simplicity that f is injective
    covmap_f_x.insert(f(key), val);
}

Note that the contravariant map is trivial in Haskell, but only a wrapper in Rust, whereas the covariant map is very simple to define in Rust and (in general) very tricky to implement in Haskell. (This is because it would require us to compute the inverse function to f).

These constructions shouldn't be surprising but I didn't want this post to start with the sentence: "Consider the bifunctor Hom . (id, Option)..."

Why I need adjunctions

When I was trying to implement with Clifford Algebras over some polynomial ring (over some indeterminates), my naïve implementation was essentially a wrapper around the type Map<I, Map<J, T>>, which is obviously not very convenient to write code for.
To make it more ergonomic (perhaps at the cost of cache locality, but that's a topic for another time), we can use monadicity of Option<T> and use the following map

mu :: Option<I -> Option<T>> -> I -> Option<T>
mu Some(g) i = g i
mu None i = None

which we can lift to an adjunction map (please excuse the pseudo Haskell+Rust)

adj :: Map<I, Map<J, T>> -> Map<(I, J), T>
    == (I -> Option<J -> Option<T>>) -> (I, J) -> Option<T>
adj g (i, j) = mu (g i)

or, in Rust's syntax something like

adj(g: Map<I, Map<J, T>>, i: I, j: J) -> Option<T> {
  if let (Some h) = g[i] {
    h[j]
  } else {
    None
  }
}

in other words, we identify a nested formal sum

$ g = sum_(i in I) ( sum_(j \in J) g(i(j)) j) i $

with the tuple sum

$ adj_g = sum_)(i,j) in (I, J)) g(i,j) (i,j) $

which is rather simple to implement in Rust.

My Question

Having to implement this for every data structure is incredibly tedious and leads to an unbelievable amount of boiler plate. Moreover, the Map<I, Map<J,<T>> -> Map<(I, J), T> thing was just one example of an adjuntion I want (free-forgetful constructions, power sets, poset closures etc. are more examples), and I want to define the functions adj or covmap, conmap once and be done with it.

  1. Do you know any crates (or trait defs, macros) that make this entire process less tedious?
  2. Often times, the underlying Map<I, T> object can be optimized (e.g. if I is Ord, Hash Signed etc.), from what I saw, the impl specialization that would make it on par with C++'s template specialization is still marked unstable. Are there any estimates on when these wil make it into stable Rust?

Feel free to ask for further clarification in case the explanation wasn't clear enough.

2

There are some non-trivial obstacles to achieve generic Map-like type for collections.
But if you do not need generic construction methods, and just lookup method, you can get away with something like:

trait Map {
    type Key;
    type Value;
    
    fn map(&self, key: Self::Key) -> Option<&Self::Value>;
}

Here is my attempt at it, see if it close to what you want: Rust Playground

There are some hairy lifetimes, and would be even harder if you want to pass keys by ref. But it is needed only once per function (adj, ...)

edit: fixed link

3

Hi, thanks for taking a look at it. I think the Rust Playground link you sent is for something else.
It looks like it's just computing something like
foldr1 intersect :: Eq a => [[a]] -> [a].

4

If you are talking about adj function, then it is an equivalent to one from your post.
Check main function and output, it uses combinations of Vec and BTreeMap as generic Maps input to adj function.

5

This is what I see when I open the Playground link:

fn main() {}

fn pairwise_intersect(x: &Vec<u32>, y: &Vec<u32>) -> Vec<u32> {/* omitted for brevity */}

pub fn intersect(arrs: &Vec<Vec<u32>>) -> Vec<u32> {/* omitted for brevity */}
6

After thinking about it more, I have a cool idea where instead of realising the outputs of the adjunction (like in Haskell curry, uncurry), we have the output be an analogue of std::string_view in C++, i.e. a shared reference to an object that behaves as if it were the object of the final type, but doesn't do any memory allocation.

To make things more concrete, here's the current library that I would like to convert into using the adjunctions: haemeah/symbolic_ga - Codeberg.org
perhaps you can find better abstractions than the ones I described.

7

I'm very sorry, the link was messed up.
Here is what I meant to link: Rust Playground