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

Thu Apr 8 14:09:16 EDT 2010

Hi Carter,

You might be interested in the 'monoids' package on hackage, which I
constructed for my own research.

http://hackage.haskell.org/package/monoids-0.1.36

This package largely covers the first half of your proposal, and provides
machinery for automatic differentiation of monoids over bimodules, which
starts to cover some of the scope you describe in the second half of your
proposal. Later revisions drastically reduce scope, in part due to the
considerations below.

I'd like to point out a few things about why you might not want to do this.

A rigorous numerical prelude is a tedious thing in Haskell to extend or to
use in practice.

I think many people would agree that Num did not strike the right balance
between generality and power. There are many perfectly good numerical types
that don't fit into the strange 'self-semi-measured ring-like thing with
equality and an available textual representation' that makes up a Haskell
Num.

However, in the absence of the ability to declare class aliases, define
default members for your superclasses, and retoactively define superclasses,
a deeper numeric prelude is an exercise in frustration.

You can view the standard mathematical hierarchy as a lattice defined by the
laws associated with the structure in question. You can start with magma,
add associativity and get semigroup, or just add a unit and get a unital
magma, but mixing the two gives you a monoid, so on and so forth. So many of
the points on this lattice have names, others are just adjectival
modifications of other more primitive concepts.

However, if you ever skip a level, and say, omit 'Quasigroup' on the way to
defining 'Loop', you'll find that the nature of Haskell makes it hard to
retrofit such a level into your hierarchy. Afterall, any users who had
defined their own 'Loop' instances before, would now have to split their
definition in half. So, on one front, these deep hierarchies are brittle.

Another problem is the drastic increase in boilerplate to instantiate
anything deep within the hierarchy. When every Field is a Magma, SemiGroup,
Monoid, QuasiGroup, Loop, Group, UnitalMagma, MultiplicativeMagma,
MultiplicativeSemiGroup, MultiplicativeMonoid, MultiplicativeQuasiGroup,
MultiplicativeLoop, MultiplicativeGroup, Ringoid, LeftSemiNearRing,
RightSemiNearRing, SemiNearRing, Rng, SemiRing, Ring, and Field with the
attendant instances to form a vector space (and hence module, etc.) over
itself and the canonical modules over the naturals (as a monoid) and
integers (as a group), the amount of boilerplate reaches a level of patent
absurdity. You have to instantiate each of those classes and provide default
definitions for properties that are clearly inferrable. Yes the
MultiplicativeQuasiGroup's notion of left and right division are uniquely
the same, but you still have to write the lines that say it, for every
instance. Template Haskell can help dull the pain, but the result seems
hardly idiomatic.

The amount of code to define a new Field-like object can baloon to well over
a hundred lines, and in the above I didn't even address how to work with
near-field-like concepts like Fields and Doubles, which don't support all of
the laws but which have the same feel.

Finally, there is the issue of adoption. Incompatibility with the Prelude is
a major concern. Ultimately your code has to talk to other people's code,
and the impedence mismatch can be high.

-Edward Kmett

On Thu, Apr 8, 2010 at 1:23 AM, Carter Schonwald <carter.schonwald at gmail.com
> wrote:

> 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
>
>
>
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100408/202d3edb/attachment.html