[Haskell-cafe] haskell gsoc proposal for richer numerical type classes and supporting algorithms

[Carter Schonwald]

Hello All,

I would like to know if there is enough community interest in following gsoc
project proposal of mine for me to write up a proper haskell gsoc app for it
. (and accordingly if there is a person who'd be up for having the mentoring
role)

Project: Alternate numerical prelude with a typeclass hierarchy that follows
that found in abstract algebra, along with associated generic algorithms for
various computations can be done on datastructures satisfying these type
clases.

In particular, the motivating idea is the following: yes it'd be useful (for
more mathematically inclined haskellers) to have a numerical prelude whose
hierarchy means something, but for even that subset of the haskell user
population, such an alternate prelude is only useful if users get extra
functionality out of that more detailed infrastructure (and I believe that
some of the infrastructure that becomes feasible would be worthwhile to the
larger haskell community).

the basic plan is as follows

1) define a typeclass hierarchy that covers everything such as  monoids -
groups - rings - fields, and various points in between.   After some
experimenting, it  has become pretty clear to me that  all of these need to
be defined indirectly with the help of template haskell so that the names of
the various operators can be suitably parameterized (so that * and + etc
aren't the only choices people have).
   This part itself isn't terribly difficult, though theres a lot of
important intermediate algebraic structures that also need to be defined,
and as I currently plan it, i'm very much inclined towards  specifying all
the required properties of each algebraic structure as testable properties,
so that in a certain sense all these type clases could be interpreted as
"adding facts" to an inference engine . This part is easy, just a lot of
support type classes which a user wouldn't often encounter or deal with
unless they're doing real math, in which case understanding them is probably
key for correctly writing the desired code anyways.

For those reading this who don't know the abstract algebra terminology:
*a monoid* is a set with an operation "+" which has an identity element, an
example would be lists and the append operation.

*a group * is a monoid where the operation is invertible, it could be
something as simple as positive rational numbers under multiplication or the
various translations and rotations that one does to 3d objects such as when
doing open gl programming where in this latter case the "*" or "+" operation
is composition of these (invertible) transformations

*a ring *will have both a "+", and a "*", and the "+" will be a group over
the set of objects in the ring and the "*" a monoid, over the objects in the
ring. a simple example would just be the integers with + and * as they
usually are. Plus some rules about 0 and 1.

*a field * would be a ring where all the nonzero elements are invertible
with respect to multiplication (ie nonzero elements form a multiplicative
group). A standard example would be rational numbers with the standard + and
*

and so forth for many other algebraic objects.

2) providing algorithmic machinery that makes this all worthwhile: in
particular there are two veins of algorithmic machinery that would be goals
of the gsoc project, one which is certainly feasible, and the other which
i'm still working out the design details for but feel is very likely.
respectively:

a) generic algorithms for various standard algebraic computational problems,
for example a generic euclidean algorithm that will work on any sort of data
structure/object/algebraic thingy that satisfies all the necessary algebraic
properties (such as multivariate polynomials!), with specialized versions
for various cases where better algorithms are known and the nature of the
representation can be exploited (eg binary gcd on the integers).
    This part of the project would essentially be me going through some
computational number theory /algebra texts such as http://www.shoup.net/ntb/
 (A Computational Introduction to Number Theory and Algebra)  and
implementing every interesting/useful algorithm both generic and specialized
variants. As haskell's numerical typeclass hierarchy currently stands, it is
impossible to implement generic versions of these algorithms in haskell, and
I don't think any widely used language aside from  haskell (except perhaps
scala?) even has the right abstraction facilities to make it feasible.
   Of course certain specialized cases would even benefit perhaps by
actually having them be in turn implemented in a more low level fashion (eg
via some external c/c++ library), but that itself is not really important
for the core project and would be beyond the scope of a single summers work.

b) because the type classes would directly encode what manipulations and
equational reasoning steps are valid, the same information  could be used to
 safely do computer assisted algebra/mathematics. In particular, the various
types which are instances of algebraic type classes (say  Field Rationals)
could also be indexed by a sort whose members are CAS and Value, so  (Field
(Rationals Value)), and depending on what the context expects, we either get
a computation, or a lightweight way of lifting mathematical expressions into
a higher order abstract syntax! Then it would be possible to do interesting
things like symbolic differentiation of  functions, eg polynomial
expressions etc.
  For this latter deliverable, theres still a few questions and problems I'd
need to work out  (such as  how names are handled and what sort of primitive
operations should be used/exposed), but nothing that seems insurmountable to
making it work, and in a fairly light weight way for the end user at that!


any constructive feedback would be very appreciated,

 please note that while irrespective of gsoc summer funding considerations
I'm planning on putting this together... the funding would  mean that I
wouldn't have a day job taking up a good chunk of my time/energy for this
coming summer.

Also, I do in fact have enough of an algorithms, pl, and math background to
undertake this project, though I'll leave that info for the gsoc app if
there proves to be an interest in the proposal.

again, thanks for any feedback!
-Carter Schonwald
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100408/04539057/attachment.html