An Algebra

Jake McArthur jake.mcarthur at gmail.com
Fri Jan 29 10:45:09 EST 2010


Since this has been my most recent area of focus, the first more
technical aspect of alt-stdlib I would like to discuss on the mailing
list is our algebra. I currently have some work on it, which you can
see at <http://patch-tag.com/r/jmcarthur/alt-stdlib/snapshot/current/content/pretty/Data/Algebra.hs>.
 It requires a preprocessor (hopefully to be replaced with a GHC
extension in the future) which you can find at
<http://github.com/dorchard/constraintTermExtensions>, which
unfortunately is difficult to build. I'm working on a cabalized
version that tracks dependencies properly, but I also might have to do
some work to make it work for GHC 6.12.

There are some issues with replacing Num with an algebra. The most
blatant, I think, is that floating point types won't actually obey
most of the laws of an algebra. There are a few approaches to this
problem (which are not necessarily mutually exclusive):

  * Pretend that they are real numbers, covering our eyes and ears to
the inaccuracies or pretending that they are just some sort of
implementation flaw.
  * Give floating point numbers their own operations with different
names from everything else, a la ML.
  * Only write instances of algebra classes for floating point that
obey the laws and don't instantiate the others.
  * Have a separate Num type class with looser restrictions on its
instances than the algebra.

My proposal is a combination of the last couple approaches. I propose
that we have an algebra some what like I have written already,
including often-called "useless" classes like Magma which don't
require any particular properties. We also have have a Num constraint
synonym which is made up of a few of the classes from the algebra,
such as Magma (Sum a) and Magma (Product a). Whatever combination we
choose, it should be enough to capture a few of the most-used
operations in Num entirely within the algebra but with very few laws
on them. Alternatively (or in conjunction, if we find a way to combine
constraint synonyms with class aliases nicely), we could make Num (and
most of the constraint synonyms in the algebra) a class alias, then we
could just define the operations in a Num instance and the instances
in the algebra are created automagically. There are some advantages to
the way I'm wanting it:

  * Num uses existing machinery from the algebra.
  * Floating point and other weird Num instances fit into the algebra
as best they can without breaking any laws.
  * Assuming class aliases, the tedium of defining tons of algebra
instances is largely done for you.
  * With constraint synonyms, getting the right combination of
instances of algebra classes gets you other algebra instances and Num
for free.
  * If we get both constraint synonyms and class aliases, these free
instances naturally work both ways. You can either define one or two
higher-level instances and get the lower-level ones for free, or you
can define a few lower-level instances and get the higher-level ones
for free.

I'd like thoughts on this proposal for Num as well as thoughts on the
algebra itself so far. Have a nice day!

- Jake



More information about the Alt-stdlib mailing list