Modeling Algebra Expressions

SPAD allows symbolic expressions to be created, this uses the Expression domain which in turn uses the Kernel domain. Expression has specific support for symbolic expressions in terms of domains/categories (such as: GcdDomain, Integer, IntegralDomain, Ring, AbelianMonoid and SemiGroup). That is the code has specific tests and chunks of code for these. Symbolic functions are explicitly listed in Expression (such as: pi, exp, log, sin, cos...).

This is very powerful for algebras, like 'ring' and 'field' that are well supported. What I would like to do is allow symbolic expressions to be created and manipulated (for example equation solvers where this is possible) for any domain I am working on. Just to make this clear, SPAD already allows a value of any type to be given an alphanumeric label, we can set this to a value given by an expression but this must always evaluate to a literal value. We can't, in general, put an unknown on the right hand side of an assignment. I would like better general support for equations and equation solvers for any domain. Also I would like to be able to express (and preferably to enforce) the axioms for a given domain.

For example, I would like to have symbolic names for elements of a Clifford algebra and to be able to create expressions involving these. I would like to be able to do this without hacking the Expression domain (which is already very messy). It would be much better for people working on the code if this were done in, or near, the Clifford algebra domain. I would not want to duplicate the general expression handling code, only separate out the parts that change for different algebras.

This may not be simple so, on this page, I would like to try to discover the top level principles.

Variables verses Combinators

I can think of two ways to approach the above issues:

In the first we would need to have 'equations'. SPAD supports equations (in 'Equation' domain) but, again, it does not seem general in that it is based on predefined operations like: +,-,*,/,1 and = so it has to have specific code for various categories of algebras. The Equation domain also has support for specific operations on the whole equation such as differentiation.

The Equation domain has a representation containing lhs and rhs both of which can be any type.

Combinators could use a language like 'Joy' which is based on the concept of a stack.

Catamorphism and Anamorphism

If we start with an algebra that has a binary operation (S,S)->S and, instead of supplying interal values we supply a symbolic value to represent a variable or unknown, we might build up a free algebra. free algebra


catamorphism anamorphism


Reduces the data structure to a required value.

Tree is a initial object in the category of F-algebras


Upwards morphism - Builds an invocation tree as an explicit data structure.

zip and iterate are examples of anamorphisms

A notation for ana(f) found in the literature is [(f)]. The brackets used are known as lens brackets.


Composition of an anamorphism and a catamorphism. Invocation tree is isomorphic to a function which processes lists.

Example Monoid

free monoid = list


monoid expression


Fold Left fold left
Fold Right fold right



So the fold operation takes a list and a monoid and returns a value


Googles MapReduce software framework.

Example Field

free field = tree?

free field

Monoid and Monad

  Monoid Monad
Definition A set: S
An operation: •: S×S->S
An element of S: e:1->S
an endofunctor: T
natural transformations:
multiplication µ: T×T-> T
unit η: 1->T
Satisfies Laws (a•b)•c=a•(b•c)
for all a,b,c
µ(η(T)) = T = T(η)

Algebraic Category

Every Algebraic Category has co-limits

The category Alg T is a free completion of Top under sifted colimits


metadata block
see also:
Correspondence about this page

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2022 Martin John Baker - All rights reserved - privacy policy.