Re: [Haskell-cafe] Proposal for restructuring Number classes
Andrew U. Frank wrote: should * always be commutative or is its use for non-commutative types acceptable? This very question caused much agony in many design meetings for the CAS Maple. The list of pros and cons on each side is quite large! There are too many really nice optimizations that one can do with a commutative, associative function (like * over commutative rings), and these are expected to be performed if ``efficiency'' matters. Hoping that the compiler will always be smart enough to tell that in case X or Y, such an optimization is valid, is quite optimistic. Until there is a way to encode that a particular instance of * is commutative, and another is not, it is much safer to have two symbols. Note that I would personally prefer a much larger set of classes, which would include encodings of *properties*, so that one could (easily, cheaply) declare some occurence of * as commutative by using the right signature. That would really require some kind of class aliases to have a hope of success. But such a large set of classes is understandably too ambitious, and better suited to Haskell''. But for a taste of what you get if you follow that route, see http://www-sop.inria.fr/cafe/Manuel.Bronstein/libaldor/html/ and also http://www-sop.inria.fr/cafe/Manuel.Bronstein/algebra/ for why the 'base' of the system needs to be complex to allow scaling. Note that the above libraries are NOT optimal, as the authors went part of the way to fully breaking down the algebraic hierarchy, but were not prescient enough 10 years ago when the basic design was being laid down to break it down all the way. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Proposal for restructuring Number classes
On Mon, Apr 10, 2006 at 12:13:55PM +0200, Andrew U. Frank wrote: there has been discussions on and off indicating problems with the structure of the number classes in the prelude. i have found a discussion paper by mechveliani but i have not found a concrete proposal on the haskell' list of tickets. i hope i can advance the process by making a concrete proposal for which i attach Haskell code and a pdf giving the rational can be found at ftp://ftp.geoinfo.tuwien.ac.at/frank/numbersPrelude_v1.pdf if i have not found other contributions, i am sorry and hope to hear about them. i try a conservative structure, which is more conservative than the structure we have used here for several years (or mechveliani's proposal). It suggests classes for units (Zeros, Ones) and CommGroup (for +, -), OrdGroup (for abs and difference), CommRing (for *, sqr), EuclideanRing (for gdc, lcm, quot, rem, div...) and Field (for /). I think the proposed structure could be a foundation for mathematically strict approaches (like mechveliani's) but still be acceptable to 'ordinary users'. I agree with Henning Thielemann about putting 'zero' in 'CommGroup' and 'one' in 'CommRing'. What is your thinking here? I would also argue for putting 'fromInteger' in 'CommRing', as discussed in the NumPrelude proposal. 'EuclideanRing' is a misnomer; a Euclidean Ring is a particular type of ring where GCD, etc. can be defined (see http://planetmath.org/encyclopedia/EuclideanRing.html), but there are other such rings, namely any Principal Ideal Domain or PID. 'IntegralDomain' is also a misnomer; I don't know what you're getting at there, but there is a well-established mathematical term 'integral domain' that means something different. o On enforcing properties: there's not currently any way to enforce properties (e.g., monad laws are not enforced); however, I believe that expected properties should be documented. o ^ and ^^ (which can actually be combined, see our proposal) are in fact quite useful, and can be implemented considerably more efficiently than a general exponentiation. If you want a complete proposal, you do need to go further. o You do impose some additional burden by changing the name of the 'Num' class, and it is worth noting that. o Mechvelliani's implementation could not be built on top of your base, because he needs to have a sample argument to 'zero' to determine, e.g., the right zero for modular arithmetic. Henning mentioned this in his response. To implement modular arithmetic with these signatures, as far as I know, you need to either separate Zero constructors or do something like the Kiselyov-Shan paper. (See, e.g., Frederick Eaton's linear algebra library recently posted to the Haskell list.) Peace, Dylan Thurston signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Proposal for restructuring Number classes
there has been discussions on and off indicating problems with the structure of the number classes in the prelude. i have found a discussion paper by mechveliani but i have not found a concrete proposal on the haskell' list of tickets. i hope i can advance the process by making a concrete proposal for which i attach Haskell code and a pdf giving the rational can be found at ftp://ftp.geoinfo.tuwien.ac.at/frank/numbersPrelude_v1.pdf if i have not found other contributions, i am sorry and hope to hear about them. i try a conservative structure, which is more conservative than the structure we have used here for several years (or mechveliani's proposal). It suggests classes for units (Zeros, Ones) and CommGroup (for +, -), OrdGroup (for abs and difference), CommRing (for *, sqr), EuclideanRing (for gdc, lcm, quot, rem, div...) and Field (for /). I think the proposed structure could be a foundation for mathematically strict approaches (like mechveliani's) but still be acceptable to 'ordinary users'. i put this proposal for discussion here and hope for suggestions how it can be improved before i put it to haskell'! andrew frank Numbers.hs Description: Binary data ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Proposal for restructuring Number classes
On Mon, 10 Apr 2006, Andrew U. Frank wrote: there has been discussions on and off indicating problems with the structure of the number classes in the prelude. i have found a discussion paper by mechveliani but i have not found a concrete proposal on the haskell' list of tickets. i hope i can advance the process by making a concrete proposal for which i attach Haskell code and a pdf giving the rational can be found at ftp://ftp.geoinfo.tuwien.ac.at/frank/numbersPrelude_v1.pdf if i have not found other contributions, i am sorry and hope to hear about them. I recently mentioned the NumericPrelude project: http://cvs.haskell.org/darcs/numericprelude/ http://cvs.haskell.org/darcs/numericprelude/src/Algebra/Core.lhs http://cvs.haskell.org/darcs/numericprelude/docs/html/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Proposal for restructuring Number classes
On Mon, 10 Apr 2006, Andrew U. Frank wrote: there has been discussions on and off indicating problems with the structure of the number classes in the prelude. i have found a discussion paper by mechveliani but i have not found a concrete proposal on the haskell' list of tickets. i hope i can advance the process by making a concrete proposal for which i attach Haskell code and a pdf giving the rational can be found at ftp://ftp.geoinfo.tuwien.ac.at/frank/numbersPrelude_v1.pdf Why are Zeros and Ones separated from the classes providing the operations? Since groups are required to have a neutral element and rings must have both a neutral additive element and a neutral multiplicative element, it makes sense to me, to couple Additive group with a zero and a Ring structure with a one. I guess you want to separate them because there are vectors and matrices of different sizes which we subsume under the same Haskell type. I have not seen a convincing solution for this problem so far. Indeed there are proposals implicit parameters, local type class instances and so on. The problem arises also for residue classes. I have worked around that problem by not comparing with a generated zero, but use a special isZero method. If I need a zero or a one in an algorithm I make it a parameter of the algorithm. Sometimes this leads to a nice generalization of an algorithm, if callers provide values different from zero. gcd+lcm, quot+rem, div+mod: In NumericPrelude quot+rem and div+mod are in separate classes. 'quot' and 'rem' need a notion of rounding towards zero. They are less general than 'div' and 'mod'. Actually I have never found an appriopriate application of 'quot' and 'rem'. When I saw them in other programs, 'div' or 'mod' were always the better choice. Also in NP 'gcd' and 'lcm' are separated from 'div' and 'mod', because the greatest common divisor cannot be always computed by the Euclidean algorithm. (^), (^^), (**): I found the distinctions of powers very useful and I would even refine them. In mathematical notation we don't respect types and we do not distinguish between powers of different types. However if we assume the most general types for both basis and exponent, the result of the power is no longer unique. Actually all possible solutions of say 1^x, where x is irrational is dense in the complex unit circle. In the past I needed the power of two complex numbers only once, namely for the Cauchy wavelet: f(t) = (1- i*k*t) ^ (-1/2 + mu2/k + i*mu1) http://www.math.uni-bremen.de/~thielema/Research/cwt.pdf http://ieeexplore.ieee.org/iel5/78/18506/00852022.pdf?arnumber=852022 However, I could not use the built-in complex power function because the resulting function became discontinuous. Of course, powers of complex numbers have the problem of branch cuts and the choice of the branch built into the implementation of the complex power is quite arbitrary and might be inappropriate. But also for real numbers there are problems: For computing (-1)**(1/3::Double) the power implementation has to decide whether (1/3::Double) is close enough to a third. If it does so it returns (-1) otherwise it fails. However, why shall 0.333 represent 1/3? It may be really meant as 333/10^15, and a real 10^15th root of (-1) does not exist. So I propose some balancing: The more general the basis the less general the exponent and vice versa. I also think the following symbols are more systematic and intuitive: any ring (provides *)^ cardinal any field (provides /) ^- integer an algebraic field ^/ rational (computing a list of powers depending on the denominator of the rational) positive real (including transcendent) ^? anything (unqiue via exponential series) That is (^-) would replace (^^), (^?) would replace (**), (^) remains and (^/) is new. Branch cuts are a problem for all functions based on logarithms, apart from log and (**) these are: asin, acos, atan, asinh, acosh, atanh. I wonder how to treat them. I thought whether a residue class type would help. However a residue class with respect to the transcendent number pi would lead to a lot of rounding problems and the residue classes could be hardly processed further. So I'm thinking about a logarithm which returns a list of possible solutions. However for real numbers the logarithm is unique. I come to the conclusion that real logarithms and associated functions are considerably different from there generalizations to complex numbers. How to resolve that in type classes? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
