Hi All,<br><br>This is in regard to previous posts about mathematical preludes.<br><br>> class Set a<br>> <br>> class (Set s) => SemiGroup s o where<br>> semigroup_op :: o -> (s,s) -> s<br>> -- closure
<br>> -- associative<br>><br>> class (SemiGroup s o) => Monoid s o where<br>> identity :: o -> s<br>><br>> class (Monoid s o) => Group s o where<br>> inverse :: o -> s -> s<br>
><br>> class Optimisable a where<br>> cost :: Set b => a -> b<br><br>First, consider a semigroup, which is a set with an associative operation. Into this structure falls Matrices with multiplication. There is scope for optimisation of a series of multiplications. Inductively for each m1 * m2 * m3 compare the cost of m1 * m2 versus m2 * m3 which can be simply obtained from the size of the index of the matrix. Thus expressions like (14,3) x (3,15) x (15,2) can be computed as (14,3) x ((3,15) x (15,2)) and not in a more expensive way.
<br><br>Furthermore, if we tag identities with a phantom type, we can eliminate needless operations like 3 + 0.<br><br>Not as much optimisation can be achieved with inverses (3 + -3) because it might be just as expensive to calculate that something is an inverse as to do actual calculation.
<br><br>So how can this optimisation be performed? Well this is a question that I put forward to you, Gentle Reader.<br><br>Static: <br><br>It seems to me that expressions the types of which are known at compile-time can be optimised by using type-level programming in combination with compiler rewrite rules,
e.g. if we have a type class SizeLarger then the expression <br><br>> semigroup_op (semigroup_op m1 m2) m3<br><br>can be rewritten as<br><br>> semigroup_op m1 (semigroup_op m2 m3)<br><br>depending upon the SizeLarger types of the various (semigroup_op _ _) function calls.
<br> <br>Another method is to manipulate the expressions as ASTs and convert to the concrete using TH.<br><br>But what about dynamic data?<br><br>Dynamic:<br><br>These are terms whose types are not known until run-time (such as would happen when loading an arbitrary matrix from a file). In this case we can't use compiler term-rewriting or TH, but what options are there? Depending upon the speed/complexity of type-checking versus computation would it not be feasible to use run-time type checking (a polymorphic Dynamic type) to achieve this optimisation? Yes there is a lot to said in favour of static type-checking, but there are cases in which it is not feasible, witness type-level bounds checking of run-time loaded matrices of unknown shape. In a program that used run-time typechecking (yes there would be a computational overhead) the dynamic stuff would be isolated from the 'trusted' statically checked program and values could only be injected through trusted entry points (
e.g. get4SquareDoubleMatrix :: Dynamic -> IO (Array ((D4 $ Sz),(D4 $ Sz)) Double).<br><br>In any case, writing 'simple' arithmetic expressions would become more cumbersome because of the overhead of annotating types and possibly moving between ASTs and the concrete. But if we a had collection of mathematically sound classes like SemiGroup, Monoid, Group, Field, etc... then these optimisations could be built into the compiler and we could sugar the programmer-side just as it has been for Monads.
<br><br>In conclusion, I put this forward as a reason for Mathematically Meaningful Numeric Classes and in obiter I am putting forward support for polymorphic Dynamic types (run-time typechecking).<br><br>Cheers,<br><br>
Vivian<br>