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.

1 post - 1 participant

Read full topic