Subject: Re: overlapping instances
Maybe I understand why Sergey wants to use overlapping instances in his
DoCon. 2 years ago I tried to the same thing in C++ (also while implementing
a computer algebra system). Overlapping instances *may* be useful, but
in combination with parametrized containers for algebraic things they are
likely to fail. Just one small example (sorry this is c++ -- I can't think
haskell late in the evening -- but the idea holds the same in haskell):
Take the ring of polynomials over some commutative ring. This *seems*
like a good candidate for a template class.
template<class T_coefficient> class poly { .... }
This is only half way, because we can also take the type of exponents as
a type parameter:
template<class T_coefficient, class T_exponent> class poly { .... }
One of the first functions I want to write for this class is the computation
of factors/gcd by using modular images. For this I need an upper bound for the
size of coefficients of the factors. The best bounds consider how the
coefficient interact with the exponents -- that is not just looking at the
given values -- it depends also on the given types. Therefor the computation
of the bound can't be hardcoded inside the class poly and it can't be coded
in any specialization for some *single* type parameter be it either T_coeff or
T_exponent. I can give a specializition involving both types, but looking
at an application the size of DoCon this gets impossible to handle.
There is another way: We see that the type parameters interact - that is their
combination should be treated as an entity *together* with the functions that
depend on that entity (like bounds). I wrote code that looks like this:
typedef xxxx complex_rational;
typedef yyyy integer;
// need a forward declaration>
template <class T_poly_trait> class poly;
struct poly_trait {
typedef complex_rational coefficient_type;
typedef integer exponent_type;
static coefficient_type factor_coeff_bound(const poly<poly_trait> &) {
.... // here comes the specialization
}
};
template <class T_poly_trait> class poly {
std::list<poly<T_poly_trait> & factorize() {
// no need for special things inside the container
bound = T_poly_trait::factor_coeff_bound(*this);
...
}
};
In the same way Sergey could handle the special algorithms in his examples
to compute the determinant of a matrix. In this case the matrix container
depends on only one type - the type of the elements - but the algorithms
depend also on the structure of the matrix (dense, sparse, modular,...) and
so we pack the algorithms together with a description of the structure of the
matrix in a type argument for the matrix container.
mail me if someone wants more info or a haskell example; I'm about to write
a paper about implementation strategies for containers of algebraic things.
pfitzen
