Hans aberg writes:
>
> For expressing algebraic relations, I think one can use universal algebra
> by factoring through the free universal algebra of a particular set of
> relations. For example, if one wants to state that a binary operator is
> commutative, one can say that is should be defined on the symmetric set of
> order two, that is the set of pairs (x, y) where (x, y) is equivalent to
> (y, x). If one wants to say that an operator is associative (with
> identity), then it factors through the free monoid, or list of the algebra
> itself, so this amount to saying that it is defined on the set of lists.
> And so on.
>
> For monads, you might perhaps try doing the same thing, by introducing a
> concept of "universal categories" and factorizing through them.
>
> Otherwise, I think that Haskell need a better way to more exactly describe
> what the object are. For example, a group G is formally a quadruple (G, e,
> *, -1; R), where e is an identity, * multiplication, -1 an inverse, and R
> some relations. Those details are wholly inexpressible in Haskell as
> matters now stand. The same thing applies to monads, which are also known
> as triples (plus relations). It is not possible to express in Haskell the
> fact even that monads are triples, even less that they have some additional
> monad relations to fulfill.
>
When a group is expressed as a class G having operations e, *, and -1,
then implicitly (via well defined semantics), a group is a quadruple,
so I don't think the quadruple need be explicit in the Haskell program.
The relation R is also implicit if properties are stated in the form
of equations concerning associativity and so on. I think providing a
way to express properties of the class is sufficient. While
universal algebra is also a mathematical framework capable of
expressing the properties, for a programming language logical formulae
is a more natural way to go.
Jerzy Karczmarczuk writes
> Perhaps, (no, certainly), I have different mathematic sensibility than
> Hans Aberg, but what I *really need* from Haskell is the possibility to
> *code* something efficiently, and not just to represent it.
>
> Saying that an operator is commutative does not help me, unless I have
> some ways to change the argument order to optimize the evaluation of
> a complex expression. This might be a dynamic problem, for example a
> Smalltalk object is (might be) able to resend automatically the message
> to its argument, with itself as the argument (switching:
> receiver<->arg);
> this enhances the possibility of forcing the type conversion.
>
> The associativity might be used to automatically optimize some recursive
> evaluations through embedding, for example transforming the recursive
> n! = n*(n-1)! into tail recursion. I know how to do that by hand.
>
> The monadic laws and some other theorems readable from the commutativity
> of some categorical diagrams were for me always a way to restructure the
> code in order to optimize it, for example (map f) . (map g) --=>
> map (f . g) is a kind of deforestation. Anyway saying that the
> associativity
> means that the operator is defined on a set of lists doesn't make
> me happy at all. But I am a mathematical troglodyte, and a
> non-constructive
> elegance in programming has no sex-appeal for me...
>
>
> Jerzy Karczmarczuk
> Caen, France
>
I agree that non constructive definitions are not what I want.
I also agree that enabling better optimizations is a good motivation
for stating properties of an object. There is another motiviation for
stating properties which is my main motivation; this is to increase
the assurance that the software works correctly.
Cheers
Peter White, Motorola
----- End Included Message -----
