OK, I was trying to avoid having to describe what I'm trying to accomplish since I don't know my audience here, but here goes.
I'm trying to represent abstract algebraic structures confusingly called "algebras". They consist of a set together with named operations on that set (I'm restricting myself to considering finite sets with finitely many operations, for obvious reasons). You can, of course, combine algebras into larger algebras through Cartesian products and Cartesian powers by considering their operations applied coordinatewise, where like-named operations are zipped together in a Cartesian product.
Representing Cartesian powers of algebras was easy enough, but when I got to products I hit a bit of a snag due to not being able to refer to arbitrary-length tuples in Rust, so I looked at the rust-lang source file on tuples and mimicked that for algebras, representing a Cartesian product of algebras as a tuple of algebras implemented as an algebra itself.
So far, so good in terms of compiling correctly. Unfortunately, I also want each algebra to have a name, and using tuples to represent Cartesian products didn't allow for that, so I then took a page from the itertools crate and altered the tuple implementation into the following:
use ::globals::*;
use super::traits::{Universe, Operation, HasUniverse, Algebra};
use ::util::horner::{horner, horner_inv};
use std::collections::HashMap;
use ::opsymbol::OperationSymbol;
use std::fmt::{Debug, Display, Formatter};
use std::fmt::Error as FMTError;
/// A `Universe` which consists of a Cartesian product of other `Universe`s.
#[derive(Eq, PartialEq, Hash, Clone, Default)]
pub struct ProductUniverse<T> {
u: T,
}
/// An `Operation` on a Cartesian product of `Universe`s.
#[derive(Eq, PartialEq, Hash, Clone, Default)]
pub struct ProductOperation<R, T> {
univ: ProductUniverse<R>,
ops: T,
}
#[derive(Eq, PartialEq, Clone)]
pub struct ProductAlgebra<Q,R,T> {
univ: ProductUniverse<Q>,
ops: HashMap<OperationSymbol,ProductOperation<Q,R>>,
name: String,
}
macro_rules! e { ($e:expr) => { $e } }
/// Implements product `Universe`, `HasUniverse`, `Operation`, and `Algebra` for tuples of a given sort. tuples must be of length at least 2.
macro_rules! product_impl {
($(($idx:tt) -> $T:ident)+) => {
impl<$($T:Universe),+> Universe for ProductUniverse<($($T),+)> {
type Item = ($($T::Item),+);
fn cardinality(&self) -> usize {
let mut ans = 1;
$(ans = ans * e!(self.u.$idx.cardinality());)+
ans
}
fn get_element(&self, n: usize) -> Option<($($T::Item),+)> {
let nn = horner_inv(n, &vec![$(e!(self.u.$idx.cardinality())),+]);
let mut ans = ($(e!($T::Item::default())),+);
$(match e!(self.u.$idx.get_element(nn[$idx])) {
Some(p) => e!(ans.$idx = p),
None => return None,
};)+
Some(ans)
}
fn get_int(&self, ob: ($($T::Item),+)) -> Option<usize> {
let mut mid = Vec::new();
$(match e!(self.u.$idx.get_int(ob.$idx)) {
Some(p) => mid.push(p),
None => return None,
};)+
Some(horner(&mid,&vec![$(e!(self.u.$idx.cardinality())),+]))
}
}
impl<$($T:Universe),+> Debug for ProductUniverse<($($T),+)> {
fn fmt(&self, f: &mut Formatter) -> Result<(),FMTError> {
f.write_str("ProductUniverse(...)")
}
}
impl<$($T:Universe),+> Display for ProductUniverse<($($T),+)> {
fn fmt(&self, f: &mut Formatter) -> Result<(),FMTError> {
f.write_str("ProductUniverse(...)")
}
}
impl<$($T:Operation),+> HasUniverse for ProductOperation<($($T::Univ),+),($($T),+)> {
type Item = ($($T::Item),+);
type Univ = ProductUniverse<($($T::Univ),+)>;
fn universe(&self) -> ProductUniverse<($($T::Univ),+)> {
self.univ
}
}
impl<$($T:Operation),+> Operation for ProductOperation<($($T::Univ),+),($($T),+)> {
fn arity(&self) -> ArityType {
self.ops.0.arity()
}
fn apply(&self, args: &Vec<($($T::Item),+)>) -> Option<($($T::Item),+)> {
let mut mids = ($({ let x: Vec<$T::Item> = Vec::new(); x}),+);
for x in args {
$(e!(mids.$idx.push(x.$idx.clone()));)+
}
let mut ans = ($(e!($T::Item::default())),+);
$(match e!(self.ops.$idx.apply(&mids.$idx)) {
Some(p) => e!(ans.$idx = p),
None => return None,
};)+
Some(ans)
}
fn compose(&self, args: &Vec<&ProductOperation<($($T::Univ),+),($($T),+)>>) -> Option<ProductOperation<($($T::Univ),+),($($T),+)>> {
let mut mids = ($({ let x: Vec<&$T> = Vec::new(); x}),+);
for x in args {
$(e!(mids.$idx.push(&x.$idx));)+
}
let mut ans = ($(e!($T::default())),+);
$(match e!(self.ops.$idx.compose(&mids.$idx)) {
Some(p) => e!(ans.$idx = p),
None => return None,
};)+
Some(ProductOperation { univ: self.univ.clone(), ops: ans })
}
fn projection(i: usize, r: ArityType, n: ProductUniverse<($($T::Univ),+)>) -> Option<ProductOperation<($($T::Univ),+),($($T),+)>> {
if r as usize >= i { return None; }
let mut ans = ($(e!($T::default())),+);
$(match e!($T::projection(i,r,n.$idx.clone())) {
Some(p) => e!(ans.$idx = p),
None => return None,
};)+
Some(ProductOperation { univ: n.clone(), ops: ans })
}
fn extend_arity(&self, r: ArityType) -> Option<ProductOperation<($($T::Univ),+),($($T),+)>> {
if r<self.0.arity() { return None; }
let mut ans = ($(e!($T::default())),+);
$(match e!(self.ops.$idx.extend_arity(r)) {
Some(p) => e!(ans.$idx = p),
None => return None,
};)+
Some(ProductOperation { univ: self.univ.clone(), ops: ans })
}
}
impl<$($T:Algebra),+> HasUniverse for ProductAlgebra<($($T::Univ),+),($($T::Op),+),($($T),+)> {
type Item = ($($T::Item),+);
type Univ = ProductUniverse<($($T::Univ),+)>;
fn universe(&self) -> ProductUniverse<($($T::Univ),+)> {
self.univ.clone()
}
}
impl<$($T:Algebra),+> Algebra for ProductAlgebra<($($T::Univ),+),($($T::Op),+),($($T),+)> {
type Op = ProductOperation<($($T::Univ),+),($($T::Op),+)>;
fn name(&self) -> String {
self.name.clone()
}
fn basic_operations(&self) -> HashMap<OperationSymbol,ProductOperation<($($T::Univ),+),($($T::Op),+)>> {
self.ops.clone()
}
}
}
}
product_impl!{
(0) -> A
(1) -> B
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
(5) -> F
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
(5) -> F
(6) -> G
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
(5) -> F
(6) -> G
(7) -> H
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
(5) -> F
(6) -> G
(7) -> H
(8) -> I
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
(5) -> F
(6) -> G
(7) -> H
(8) -> I
(9) -> J
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
(5) -> F
(6) -> G
(7) -> H
(8) -> I
(9) -> J
(10) -> K
}
product_impl!{
(0) -> A
(1) -> B
(2) -> C
(3) -> D
(4) -> E
(5) -> F
(6) -> G
(7) -> H
(8) -> I
(9) -> J
(10) -> K
(11) -> L
}
After changing this, I started getting the compiler overflowing its stack in the structure representing Cartesian powers (which I hadn't changed, so I assume the problem is being generated by the interaction between products and powers somehow).
As you can probably tell, I'm not so good at writing documentation, for which I apologize.
Edit: I should probably mention that ArityType is u8.