Re: Rambling on numbers in Haskell

[Fergus Henderson]

On 02-Aug-1998, Jan Skibinski <[EMAIL PROTECTED]> wrote:
> 
> I've been recently working on yet another Haskell server, and when
> testing its safety limits on numerical examples, I realized that
> there are several quite annoying problems with Haskell numerical
> types and classes.
> 
> +   Many library functions, which operate on Int, return value 0
> or faulty negative values on overflow condition. Since there
> is no exception mechanism built into Haskell,

Yes, that is a problem; but I hear that people are working on it.
For an indication of what the solution will look like, see the
recent long discussion about exceptions on this mailing list.

> +   Hugs is supplied with the type Number. According to its
> author: "Fixed width integers with overflow detection..
...
> My comment is that the chosen name "Number" is here a very
> unfortunate choice:

I strongly agree here.

> +   Haskell extension libraries define a bunch of Word types. 
> An attempt to show that Haskell can be numerically efficient?

Sure, why not?

> +   Although Prelude numeric classes are well designed from point
> of view of classification, the abundance of numeric classes
> makes them difficult to use

It's hard for a single design to satisfy everyone, I suppose.

If you have concrete suggestions on how to make them easier to use,
by all means speak up.

> +   Yet again - as it has happened with other languages, someone
> has decided that complex numbers are somehow not as important
> as other numbers.

Seems eminently reasonable to me.  Complex numbers are NOT as
important for the vast majority of users.  Furthermore,
complex numbers can easily be implemented using records
and the basic numerical types, whereas the basic numerical
types cannot be implemented efficiently using other language
constructs.

> At least Haskell acknowledges that they exist,
> yet they are relegated to a periferial library - an icing on
> a cake.

Exactly where the should be, IMHO.

> But anyone working in physics or engineering would tell you
> otherwise: complex numbers are very important in daily usage.

So those people should use that library!

How hard is it to write "import Complex"?

> However, class Complex in Haskell is tied up to Floating numbers,
> just beacuse other classes, such as Rational, do not know how to
> take square roots or deal with trigonometry, exponentials or
> hyperbolics.
> 
> But where on Earth it is said that the domain of Complex numbers
> should be restricted to Float or Double? Why not Rationals as
> well?

This is a legitimate criticism.  It might well make sense to have
a complex number package that supports such types.

Of course, no-one is stopping you from writing such a package ;-)

-- 
Fergus Henderson <[EMAIL PROTECTED]>  |  "I have always known that the pursuit
WWW:   |  of excellence is a lethal habit"
PGP: finger [EMAIL PROTECTED]| -- the last words of T. S. Garp.

Re: Rambling on numbers in Haskell

[Jon . Fairbairn]

On  3 Aug, [EMAIL PROTECTED] wrote:
> so sqrt :: (Numeric n, Floating f) => n -> f

whoops!  I meant to say 
sqrt :: (Numeric n,  Numeric f) => n -> f

or something - the important bit was that the result type shouldn't be
constrained to be the same as the argument, because while sqrt int is
meaningful it doesn't usually give an int result.  What you get back
should depend on what you use it for.

-- 
Jon Fairbairn [EMAIL PROTECTED]
18 Kimberley Road[EMAIL PROTECTED]
Cambridge CB4 1HH  +44 1223 570179 (pm only, please)

Re: Rambling on numbers in Haskell

[Jon . Fairbairn]

On  3 Aug, Jan Skibinski wrote:
>> How hard is it to write "import Complex"?
>> 
> 
>   Not hard at all, but I think I did not make myself
>   clear in my previous post. Here is the clarification:
> 
>   One of the benefits of having Complex closely coupled
>   with other numbers

That of itself is not an argument for its inclusion in the language
core rather than in a library.  I think that there is a general
agreement that the number hierarchy needs an overhaul, which could go
a long way towards adressing your complaints.

> is its potential utilization in error handling.

> So far, evaluation of sqrt (-1) produces unrecoverable error.

I think that there is some confusion wrt types here.  If you are
hoping for a floating answer, sqrt (-1) has to produce an error.
While in some cases a Number type (like Miranda) may be useful, I
think the 'proper' solution in most cases is to make the types of
things like sqrt overloaded to reflect their properties.

so sqrt :: (Numeric n, Floating f) => n -> f

>   Not only sqrt, but a bunch of other functions could be
>   rescued in a similar way:
> 
>   log (-1)

same overloading as sqrt, then

>   asin (4/3) - currently interpreted as Floating, produces NaN

different issue (press the button on Kent for details ;-)

>   Anyone can design a complex number library. The task is
>   not much more complex (pun intended:-) than dsigning
>   the type Point.
>   What is difficult though is to make Complex a citizen
>   of the world of existing numbers.

Right, but it should be done via a class hierarchy, not by squishing
all the numbers into one type.

-- 
Jon Fairbairn [EMAIL PROTECTED]

Re: Reply on Numerics

[Hans Aberg]

At 16:00 +0400 98/08/03, S.D.Mechveliani wrote:

>Not only Complex but the Real numbers too are impossible to be presented
>adequately algorithmically.

  Strictly speaking, the "real numbers" should be called floating numbers,
which one usually does in computer contexts if being more accurate.

  Hans Aberg
  * Email: Hans Aberg 
  * Home Page: 
  * AMS member listing: 

Re: Rambling on numbers in Haskell

[Hans Aberg]

>But where on Earth it is said that the domain of Complex numbers
>should be restricted to Float or Double? Why not Rationals as
>well?

  In pure math, given a ring $R$, one speaks about its complexification
$R_\C = $R \tensor_\Z \Z[i]$ (using LaTeX commands and \tensor = \otimes,
\C = \mathbb{C}, \Z = \mathbb{Z}), where $\Z[i]$ are the integers extended
with a complex unit $i$. More explicitly, the complexification $R_\C$ will
consist of pairs $r + i s$, where $r, s \in R$, $i$ is a formal symbol, and
addition, multiplication and so on uses the rules for the usual complex
numbers.

  So, why not add a type "Complexify(R)" of a ring R to Haskell?

  Hans Aberg
  * Email: Hans Aberg 
  * Home Page: 
  * AMS member listing: 

Reply on Numerics

[S.D.Mechveliani]

Jan Skibinski  <[EMAIL PROTECTED]>  wrote on 2 Aug 1998 

(Subject:  Rambling on numbers in Haskell)


> ... I realized that there are several quite annoying problems with 
> Haskell numerical types and classes.
> ...
>  Yet again - as it has happened with other languages, someone
>  has decided that complex numbers are somehow not as important
>  as other numbers. At least Haskell acknowledges that they exist,


Not only Complex but the Real numbers too are impossible to be presented
adequately algorithmically. 
In this sense, they differ from Rational greatly.
Therefore, i propose for Haskell to name RealLike what it might call
Real, and ComplexLike - what it might call Complex.

On the other hand, Integer is indeed more important than Complex.
Because ComplexLike can be programmed easily via Integer.
  


> But where on Earth it is said that the domain of Complex numbers
> should be restricted to Float or Double? Why not Rationals as
> well?
> ... 
> Why is it that Maple, Matlab, Mathematica and other bunch of
> symbolic languages and also the calculators from the field of number
> theory can handle numbers smoothly without pestering the user with
> the messages of the kind "Int is not an instance of class 'Fractional'"?
> Are we becoming the slaves of the type system that you guys invented
> for some other, otherwise undoubtely important, reasons?


The main issue on  Maple, Matlab, Mathematica ... is that they are the
computer algebra systems.
And Haskell is an universal programming language and tool.
It would be more natural to write an application in Haskell which would
do what these CA programs do.
In particular, i am developing such a program 
(DoCon-1.07   );  hope to release DoCon-2 this year.
Real and Complex (as Float) are not yet there, but, say, Rational-Complex,
Gaussian integers, and such, they are.


>... But I am sure there are plenty of Haskell afficionados with their 
> background in Number Theory that could made a serious revision of 
> numbers in Haskell. Time is probably right - considering that Haskell 2 
> is in its incubations stage.


I am going to suggest the more appropriate algebraic class hierarchy for 
Haskell-2. 
I wonder how lowd the community will start cussing.
This will touch the so-called numeric classes too
(Number classes are inside the Algebraic ones, but Haskell-1.4 somehow 
does not notice the difference at all).
For, probably, many people think that Haskell-2 has not to care for not 
breaking the Haskell-1.4 apllication code.


> Ideally, complex numbers should be incorporated somehow into
> basic numbers. I know, some purists would disagree, because
> Complex does not fit well into Ord class, but for me this is
> just a question of a definition or reorganization of classes.
> You can still somehow compare complex numbers - be it via
> magnitude or some other means. I would love to see sqrt (-1)
> producing complex answer, and not failing on me. I would like
> to have logaritms of negative numbers, arcsin's of x > 1, etc., etc.


`Complex' does not need the ordering (>).
Because it cannot agree well with (*).
But (>) is not necessary for incorporating of Complex.


Regards,


--
Sergey Mechveliani
[EMAIL PROTECTED]

Re: Reply on Numerics

[Jan Skibinski]

> 
> Not only Complex but the Real numbers too are impossible to be presented
> adequately algorithmically. 
> In this sense, they differ from Rational greatly.
> Therefore, i propose for Haskell to name RealLike what it might call
> Real, and ComplexLike - what it might call Complex.
> 
> On the other hand, Integer is indeed more important than Complex.
> Because ComplexLike can be programmed easily via Integer.

I am not saying otherwise, I am just saying that other
numbers should be aware of Complex for variety of reasons.
I think I answered it somewhere else.

Rational is currently defined by two Integers and Complex could be
defined by two Rationals, rather than by two Floatings.
But the Rational would have to be generalized, so one
could do the same basic oparations on Rationals as is currently
defined for Floatings: sqrt, log, sin, sinh, etc.

For me Floating is just one possible approximation of Real.
Some people do not even realize how punctured a Double
can be when they try to use it as a representation of a big
number. After all the logarithmic scale is used here and one
should be aware of really big "black holes" for big numbers.
I know of some poor souls that tried to use it for business
applications.
Imagine millions of dollars misteriously vanishing from some
corporate account, because Double was used to represent
dollars and cents? :-)

In contrary, sticking for a moment to a continued fraction, I can
think of any desired accuracy of a representation of an Irrational
number that can achieved this way.
For example, say you defined sqrt this way

sqrt :: Rational -> Rational -> Rational

then you could call sqrt to compute square root of 2 with
an accuracy 10^(-9), for example:

sqrt (1/10) 2 ==> 66922 % 47321 ==> 1.414213562

For this you'd have to evaluate 13 steps in continued
fraction expansion. But if you do not care for any accuracy
better than 0.001 then 5 steps would suffice. You just
specify the accuracy and the sqrt function would do all
what is needed to achieve it.

Same way we could compute pi, e, sinh, etc. And as I
was saying in my original post - there are better ways
of doing this. And more efficient too! What I understand,
the efficient implementations of Irrationals are around
the corner.

> 
> The main issue on  Maple, Matlab, Mathematica ... is that they are the
> computer algebra systems.
> And Haskell is an universal programming language and tool.

So? Eiffel was also conceived as a general language,
until they realized the need for math library.
Same with C and other languages. And now you have
wavelets and The Best Fourier Transform On The West
(or whatewever they call it) implemented in C.


> It would be more natural to write an application in Haskell which would
> do what these CA programs do.
> In particular, i am developing such a program 
> (DoCon-1.07   );  hope to release DoCon-2 this year.
> Real and Complex (as Float) are not yet there, but, say, Rational-Complex,
> Gaussian integers, and such, they are.

Interesting, but what I sense here is an unnecessary complexity.
But I look forward to seeing it.

> 
> I am going to suggest the more appropriate algebraic class hierarchy for 
> Haskell-2. 
> I wonder how lowd the community will start cussing.
> This will touch the so-called numeric classes too
> (Number classes are inside the Algebraic ones, but Haskell-1.4 somehow 
> does not notice the difference at all).
> For, probably, many people think that Haskell-2 has not to care for not 
> breaking the Haskell-1.4 apllication code.

I've already seen a statement saying that Haskell-2 does
not have to be compatible with Standard Haskell.

Jan

RE: Rambling on numbers in Haskell

[Mark P Jones]

Hi Jan,

| ... I realized that
| there are several quite annoying problems with Haskell numerical
| types and classes.
| ...
| +   Hugs is supplied with the type Number. According to its
| author: "Fixed width integers with overflow detection.. Unlike
| Int, overflows are detected and cause a run-time error...
| A fairly messy hack, but at least it works...".
| 
| My comment is that the chosen name "Number" is here a very
| unfortunate choice: it suggests generality, but in fact this
| is just only a better Int.

Please don't blame Haskell for the Number library; it isn't part
of any Haskell standard.

The author that you refer to is me, and the program was, as the
comment suggests, nothing more than a quick hack.  I originally
included it in the Hugs distribution Hugs in the hope that it might
be useful to someone, perhaps more as an example using restricted
type synonyms than as a practically oriented library.  And it's
lurked there ever since.  I'm concerned that people might mistake
such things as anything more than this.

As for the name, the library was originally intended to provide
something more like Miranda's numeric datatype, incorporating
floating point and integer values.  Adding two large integers
would then result in a change of representation rather than an
overflow.  So the first step was to detect overflow.  I never
got around to the next step ... you might want to try it yourself,
possibly incorporating complex numbers too.  In any case, that's
why it was called "Number".

Finally, I think there is a general warning in the Hugs documentation
that Hugs is not really suitable for numeric work.  For example, the
default representation of both single and double precision floating
point numbers is single precision ... in both cases.  This may/will
change in future incarnations, I just don't want you to get the wrong
impression now.

Hope this clears things up!

All the best,
Mark

Re: Rambling on numbers in Haskell

[Alastair Reid]

To answer just one of Jan Skibinski's questions: 

> +   Haskell extension libraries define a bunch of Word types. 
> An attempt to show that Haskell can be numerically efficient?

The motivation for adding Word{8,16,32,64} was to make it easier to
interface to foreign libraries which use these types.  The names
are supposed to be completely unambiguous so that library designers
know exactly what they're getting.

The design does not include a type "Word" which, like "Int" could
contain as many bits as the implementor felt like.

We argued for a while about including a type for unsigned ints of
unbounded size.  We didn't do so because we can always add it later
and because we had no compelling need.  (The lack of compelling need
is important because it's much easier to design something right if 
you're planning to use it next week.)


So, no I don't think we were worrying about efficiency when we added these.
In fact, Word{8,16,32} are represented as 32 bit numbers in Hugs
and most arithmetic operations are just normal 32 bit operations.
We only convert them to the right size when we compare them, print
them, etc (ie for operations where the result will be affected).


-- 
Alastair Reid  Yale Haskell Project Hacker
[EMAIL PROTECTED]  http://WWW.CS.Yale.EDU/homes/reid-alastair/

Re: Rambling on numbers in Haskell

[Jan Skibinski]

Hi Jon:

> 
> whoops!  I meant to say 
> sqrt :: (Numeric n,  Numeric f) => n -> f
> 
> or something - the important bit was that the result type shouldn't be
> constrained to be the same as the argument, because while sqrt int is
> meaningful it doesn't usually give an int result.  What you get back
> should depend on what you use it for.

OK, I agree here. Mine was just some quick example, and
I do not promote squishing everything into one type.

As long as my other example with eigenvalues works for me,
that is: as long as I can hope for a vector of reals
OR complex, I am satisfied. But I definitely do not want
an error, because I know up front that some solution exists
- be it real or complex. Sometimes I can predict which one,
but often I cannot.

Jan

RE: Rambling on numbers in Haskell

[Jan Skibinski]

Hi Mark:

> Please don't blame Haskell for the Number library; it isn't part
> of any Haskell standard.

I did not try blaming anyone or anyting. I was hoping
to initiate some constructive flow of solutions. Thank
you for your explanation. I had somehow anticipated your
answer in relation to the name "number" - thinking that
there must have been a good reason for chosing it.:-)

> So the first step was to detect overflow.  I never
> got around to the next step ... you might want to try it yourself,
> possibly incorporating complex numbers too.  In any case, that's
> why it was called "Number".

I'd like to, but I do not want to repeat the effort
of others. Maybe someone already has something advanced
enough? I wish to hear from other people first.

Jan

Re: Instance Declarations are Universal

[Keith S. Wansbrough]

> | [..]
> | sufficient restrictions in this area Haskell's type system would
> | become undecidable, I decided to demonstrate this directly. In this
> 
> It's great that you've done this, but I think someone ought to
> point out that this result, and even the basic method, is not
> actually new:  You might want to find a copy of the proceedings

Sorry, I never intended to imply this was new -- of course it's known
that this type system is undecidable.  My note was essentially a neat
party trick that I decided to distribute more widely.  My apologies to
anyone who was misled by my earlier wording.

Regards,

--KW 8-)
-- 
: Keith Wansbrough, MSc, BSc(Hons) (Auckland) -:
: PhD Student, Computing Science, University of Glasgow, Scotland. :
: Native of Antipodean Auckland, New Zealand: 174d47' E, 36d55' S. :
: http://www.dcs.gla.ac.uk/~keithw/  mailto:[EMAIL PROTECTED]   :
:--:

Re: Rambling on numbers in Haskell

[Jan Skibinski]

Hi Fergus:
> 
> How hard is it to write "import Complex"?
> 

Not hard at all, but I think I did not make myself
clear in my previous post. Here is the clarification:

One of the benefits of having Complex closely coupled
with other numbers is its potential utilization
in error handling. So far, evaluation of sqrt (-1)
produces unrecoverable error. But the answer could
be the legal complex 0:+1 - providing that the instance
(-1) (currently Floating a) knows about Complex.

For the sake of the argument, I assume here that
in some revised version of Haskell there is a class
Number, and the operation sqrt is defined as:

sqrt :: Number -> Number

sqrt x = 
 if isComplex x then
sqrtComplex x
 else if (x < 0) then
0:+sqrtReal (-x)
 else
sqrtReal (x)

This implies that Complex and other numbers are equal
partners in the world of numbers. But that would require
that the entire hierarchy of numbers should be somehow
revised.

Not only sqrt, but a bunch of other functions could be
rescued in a similar way:

log (-1)
asin (4/3) - currently interpreted as Floating, produces NaN
acos (4/3)
etc.

The problem is not new at all. I think that a typical
approach to incorporating Complex into a typical library
in a typical language is as follows:

1. Initial design stage:
   Complex? Who cares, it is not that important!
2. Later:
   Someone discovers that Complex might be useful,
   so a library is written as an add-on. However,
   in some languages this is already too late,
   because the library implementation cannot be
   made efficient and would require some support from
   the language itself. Example: Eiffel.

Let me describe what happened with Eiffel. One day
Bertrand Meyer realized that in order to find a wider
audience they must prove that Eiffel is perfectly suitable
for scientific/engineering applications, and is not
just a general purpose language - as you have put
it in your message.

For this they needed a mathematical library. They
decided to build an object oriented interface to
the existing NAG library - C version. Suddenly
they "discovered" the world of complex numbers, because
a majority of NAG functions from linear algebra
and from nonlinear equations produce complex answers. 

Say you want to find the eigenvalues of Real matrix. 
If the matrix is square and symmetric than the eigenvalues
are real, otherwise they are complex.

Say you want to find roots of some polynomial.
You start with real coefficients, but in many cases
you end up with complex roots. Real roots are just
a special case.

Eiffel is a strongly typed language. By the time
we started the project (I am a co-designer of
the Mathematical Library for Eiffel, Paul Dubois was
the project leader) it already had a very elaborate
hierarchy of numbers. Suddenly there was a problem: how
to fit complex into the scheme of things, how to handle
two types of answers in the same time.

We did not have much choice and our complex numbers had
to be limited to the Double domain. That's why I am trying
to warn you about this issue - before it's too late.

We managed, but it was not so easy. I do not work
with Eiffel any more, but if you search for my
name in association with Eiffel you will come across
some critique of my portion of the design. Some
people even like it.:-)


In summary:
---

Anyone can design a complex number library. The task is
not much more complex (pun intended:-) than dsigning
the type Point.
What is difficult though is to make Complex a citizen
of the world of existing numbers.
 
Jan