Jonathan Cast reacts to Don Stewart statement about PI:

...

It's in the Floating class.

Yes. But it doesn't have a default implementation. That strikes me as odd, considering the mathematical and actual correctness of

class Floating sigma where pi = acos (-1) ...

So, you assume that acos should have a *default* implementation in the Floating class? Propose it, please. Note, BTW that from the viewpoint of "actual" correctness, it would be better to have PI as exact as possible, while acos, well, it is a trans- cendental function, whose representations are usually approximate... Jerzy Karczmarczuk

Dan Piponi writes:

jerzy.karczmarczuk wrote:

...

So, you assume that acos should have a *default* implementation in the Floating class? Propose it, please.

I don't think the proposal makes any such assumption. It implies only that *if* you provide acos, pi will be provided for you automatically if you want.

Yes, sorry, I slipped... I was so against the acos(-1) /or atan(...)/ solution, that I wrote anything...

...

Note, BTW that from the viewpoint of "actual" correctness, it would be better to have PI as exact as possible, while acos, well, it is a trans- cendental function, whose representations are usually approximate...

pi is a transcendental number, same argument applies.

No. There is a difference between one constant which can be represented with the maximum precision possible, and a procedure which necessarily uses some approximations, and whose local precision for some argument will be typically much lower than the machine one. Jerzy Karczmarczuk

Dan Piponi wrote:

The reusability of Num varies inversely with how many assumptions you make about it.

A default implementation of pi would only increase usability, not decrease it. If you need a specialized definition of pi in your instance, you would provide it, just as you do now. If pi makes no sense in your instance and you need it to be an error, you would define pi = error "pi in your face", just as you do now. And in the most common case, you would do nothing, instead of redifining pi in the obvious way, as you need to do now. -Yitz

jerzy.karczmarczuk@info.unicaen.fr wrote:

Yitzchak Gale writes:

...

Dan Piponi wrote:

...

The reusability of Num varies inversely with how many assumptions you make about it.

A default implementation of pi would only increase usability, not decrease it.

Suppose I believe you. (Actually, I am afraid, I have doubts.) Can you provide some examples of this "increased usability"? If possible, with a *relevant* context, which shows that PI should belong by default to the class Floating (whatever we mean by that...) Somehow I do not only think that the default implementation would be good for nothing, but that putting PI into Floating as a class member, serves nobody.

Putting 'pi' in the same class as the trigonometric functions is good design.

I would be happy to learn that I am mistaken, but if it is just to save 5 seconds of a person who wants to pass smoothly between floating numbers of single and double precision... Jerzy Karczmarczuk

Moving smoothly from single to double precision was much of the motivation to invent a mechanism like type classes in the first place. There are two things in Floating, the power function (**) [ and sqrt ] and the transcendental functions (trig functions,exp and log, and constant pi). Floating could be spit into two classes, one for the power and one for the transcendental functions. And I would bet that some of the custom mathematical prelude replacements do this. If you do not want 'pi' in a class named Floating then you have to move all the transcendental stuff with it. If you do not want 'pi' in any class, then you cannot reasonably put any of the transcendental functions in a class. This would really degrade the API. -- Chris

On 2007-10-10, jerzy.karczmarczuk@info.unicaen.fr wrote:

ChrisK writes:

...

Putting 'pi' in the same class as the trigonometric functions is good design.

If you wish so... But: Look, this is just a numeric constant. Would you like to have e, the Euler's constant, etc., as well, polluting the name space? What for?

It's there in the form (exp 1), after all. Yeah, you can get pi from (log i), but the multi-valuedness is annoying. Not an issue with exp.

The power is an abomination for a mathematician. With rational exponent it may generate algebraic numbers, with any real - transcendental... The splitting should be more aggressive. It would be good to have *integer* powers, whose existence is subsumed by the multiplicative s.group structure. But the Haskell standard insists that the exponent must belong to the same type as the base...

Yes, this is an issue. I wish there were a serious plan for reworking the numeric hierarchy for Haskell', but no one seems to interested. I've thought about writing something up, but with it not entirely clear what subset of MPTCs, FunDeps, and ATs will be in, that makes a design a bit trickier. class Exponential a where (^) :: (Integral b) => a -> b -> a

What?? But it is just a numerical constant, no need to put it into a class, and nothing to do with the type_classing of related functions. "e" is not std. defined, and it doesn't kill people who use exponentials.

As I said above, it effectively is. And, after all, 1, 2, 3, are constants of the typeclass Integral a => a, and 0.0, 1.348, 2.579, 3.7, etc. are in Floating a => a. So why not pi? -- Aaron Denney -><-

Actually, it is a constant: piDecimalExpansion :: String. A translation from piDecimalExpansion :: String to pi :: Floating a => a is already well defined via read :: Read a => String -> a Any definition of pi in the Floating class that differs from (read piDecimalExpansion) is erroneous. I propose the above as the default definition of pi. Dan Weston ok wrote:

Someone wrote about pi:

| But it is just a numerical constant, no need to put it into a class, and

...

...

nothing to do with the type_classing of related functions. "e" is not std. defined, and it doesn't kill people who use exponentials.

But it *isn't* "A" numerical constant. It is a *different* constant for each instance of Floating. In this respect, it's not unlike floatRange, which is just "a" constant (a pair of integers), but is different for each RealFloat instance.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

David Benbennick wrote:

On 10/10/07, Dan Weston wrote:

...

Actually, it is a constant: piDecimalExpansion :: String.

Where is this constant defined?

...

A translation from piDecimalExpansion :: String to pi :: Floating a => a is already well defined via read :: Read a => String -> a

Any definition of pi in the Floating class that differs from (read piDecimalExpansion) is erroneous. I propose the above as the default definition of pi.

piDecimalExpansion, if defined, would be an infinite length string.

It would need to be added. The fact that it has infinite length is no problem. It is countable infinite, and algorithms exist to compute this lazily.

The expression

read $ "0." ++ repeat '1' :: Double

is Bottom. So even if you had piDecimalExpansion, it isn't clear how to use that to define pi.

Ouch. Why is that bottom? Any finite dense numeric type can depend on only a finite number of digits.

On 11 Oct 2007, at 1:34 pm, Dan Weston wrote:

Actually, [pi] is a constant: piDecimalExpansion :: String.

No, that's another constant.

A translation from piDecimalExpansion :: String to pi :: Floating a => a is already well defined via read :: Read a => String -> a

Wrong. piDecimalExpansion would be infinite. pi is, after all, a transcendental number. It can be computed incrementally by a finite algorithm, true. The problem is that read has to read *all the way to the end*, and there is no end. (More precisely, either to the end of the string or to the first character that is not part of a floating point literal.)

Any definition of pi in the Floating class that differs from (read piDecimalExpansion) is erroneous.

In effect, you are proposing that the only non-erroneous definition of pi is bottom. I don't think that is very helpful.

On Wed, Oct 10, 2007 at 12:29:07PM +0200, jerzy.karczmarczuk@info.unicaen.fr wrote:

ChrisK writes:

...

There are two things in Floating, the power function (**) [ and sqrt ] and the transcendental functions (trig functions,exp and log, and constant pi).

Floating could be spit into two classes, one for the power and one for the transcendental functions.

The power is an abomination for a mathematician. With rational exponent it may generate algebraic numbers, with any real - transcendental... The splitting should be more aggressive. It would be good to have *integer* powers, whose existence is subsumed by the multiplicative s.group structure. But the Haskell standard insists that the exponent must belong to the same type as the base...

I suppose you're unfamiliar with the (^) operator, which does what you describe? It seems that you're arguing that (**) is placed in the correct class, since it's with the transcendental functions, and is implemented in terms of those transcendental functions. Where is the abomination here? -- David Roundy Department of Physics Oregon State University

On Wed, 10 Oct 2007, David Roundy wrote:

On Wed, Oct 10, 2007 at 12:29:07PM +0200, jerzy.karczmarczuk@info.unicaen.fr wrote:

...

ChrisK writes:

...

There are two things in Floating, the power function (**) [ and sqrt ] and the transcendental functions (trig functions,exp and log, and constant pi).

Floating could be spit into two classes, one for the power and one for the transcendental functions.

The power is an abomination for a mathematician. With rational exponent it may generate algebraic numbers, with any real - transcendental... The splitting should be more aggressive. It would be good to have *integer* powers, whose existence is subsumed by the multiplicative s.group structure. But the Haskell standard insists that the exponent must belong to the same type as the base...

I suppose you're unfamiliar with the (^) operator, which does what you describe?

It seems that you're arguing that (**) is placed in the correct class, since it's with the transcendental functions, and is implemented in terms of those transcendental functions. Where is the abomination here?

(**) should not exist, because there is no sensible definition for many operands for real numbers, and it becomes even worse for complex numbers. The more general the exponent, the more restricted is the basis and vice versa in order to get sound definitions. http://www.haskell.org/pipermail/haskell-cafe/2006-April/015329.html

On Wed, Oct 10, 2007 at 08:53:22PM +0200, Henning Thielemann wrote:

On Wed, 10 Oct 2007, David Roundy wrote:

...

It seems that you're arguing that (**) is placed in the correct class, since it's with the transcendental functions, and is implemented in terms of those transcendental functions. Where is the abomination here?

(**) should not exist, because there is no sensible definition for many operands for real numbers, and it becomes even worse for complex numbers. The more general the exponent, the more restricted is the basis and vice versa in order to get sound definitions.

Would you also prefer to eliminate sqrt and log? We've been using these functions for years (in other languages) without difficulty, and I don't see why this has changed. I think it's quite sensible, for instance, that passing a negative number as the first argument of (**) with the second argument non-integer leads to a NaN. -- David Roundy Department of Physics Oregon State University

Henning Thielemann wrote:

It would better to disallow negative bases completely for (**), because integers should be explicitly typed as integers and then (^^) can be used. I have already seen (x**2) and (e ** x) with (e = exp 1) in a Haskell library. Even better would be support for statically checked non-negative numbers.

Um... Data.Word? (Now if you'd said "strictly positive", that's harder...)

David Roundy:

jerzy.karczmarczuk:

...

The power is an abomination for a mathematician. With rational exponent it may generate algebraic numbers, with any real - transcendental... The splitting should be more aggressive. It would be good to have *integer* powers, whose existence is subsumed by the multiplicative s.group structure. But the Haskell standard insists that the exponent must belong to the same type as the base...

I suppose you're unfamiliar with the (^) operator, which does what you describe?

Sorry for being imprecise. I know (^), certainly, I wanted to suggest that the power should THEN belong to Num; if a multiplication is defined, surely the integer power as well, although this is somewhat delicate, since (*) defines a semi-group. That's why (^) for negative exponent, yells. And that's why we have also (^^) for Fractionals, which calls recip for the negative exponent.

... Where is the abomination here?

Having THREE different power operators, one as a class member, others as normal functions. Do you think this is methodologically sane? ======= Other message:

Would you also prefer to eliminate sqrt and log? We've been using these functions for years (in other languages)... I think it's quite sensible, for instance, that passing a negative number as the first argument of (**) with the second argument non-integer leads to a NaN.

As you wish. But, since this is an overloaded class member, making it sensitive to the exponent being integer or not, is awkward. And perhaps I would *like* to see the result being complex, non NaN? Oh, you will say that it would break the typing. NaN also does it, in a sense. And this suggests that the type a->a->a is perhaps a wrong choice. Of course, this implies a similar criticism of log and sqrt... (One of my friends embeds the results of his functions in a generalization of Maybe [with different Nothings for different disasters], and a numerical result, if available, is always sound.) I am not sure whether Henning's ideas convince me entirely, and his statement "In mathematical notation we don't respect types" seems to be perhaps too strong (unless 'notation' means just the notation, which doesn't "respect anything"), but the relation between mathematical domains and the type system should one day be sanitized. Jerzy Karczmarczuk

On Wed, 2007-10-10 at 12:29 +0200, jerzy.karczmarczuk@info.unicaen.fr wrote:

ChrisK writes:

...

Putting 'pi' in the same class as the trigonometric functions is good design.

If you wish so... But: Look, this is just a numeric constant. Would you like to have e, the Euler's constant, etc., as well, polluting the name space? What for?

...

Moving smoothly from single to double precision was much of the motivation to invent a mechanism like type classes in the first place.

Pardon? I think I remember the time when type classes have been introduced. The motivation you mention is not very visible, if at all... Actually, the numerical hierarchy was - as the French would say - "bricolée" with plenty of common sense, but without a decent methodology... The type classes is a splendid invention, much beyond any numerics. Besides, most people who *really* need FlP numerics use only the most precise available, the "single precision" stuff is becoming obsolete.

...

There are two things in Floating, the power function (**) [ and sqrt ] and the transcendental functions (trig functions,exp and log, and constant pi).

Floating could be spit into two classes, one for the power and one for the transcendental functions.

The power is an abomination for a mathematician. With rational exponent it may generate algebraic numbers, with any real - transcendental... The splitting should be more aggressive. It would be good to have *integer* powers, whose existence is subsumed by the multiplicative s.group structure. But the Haskell standard insists that the exponent must belong to the same type as the base...

Check out the type of (^). It's a different operator, but they exist... jcc

jerzy.karczmarczuk@info.unicaen.fr wrote:

Somehow I do not only think that the default implementation would be good for nothing, but that putting PI into Floating as a class member, serves nobody.

Are you aware that it already is in the Floating class? This discussion is not about adding it, but about whether or not it should have a default. Are you suggesting pi should be removed from the Floating class? Then, what type would you give pi? Given that pi is often used with sin, as in "sin (t * pi)" it would seem very odd if pi forced that to be monomorphic: \t -> sin t -- polymorphic \t -> sin (t*pi) -- monomorphic ? Jules

jerzy.karczmarczuk@info.unicaen.fr wrote:

...

This discussion is not about adding it, but about whether or not it should have a default. Are you suggesting pi should be removed from the Floating class? Then, what type would you give pi?

First, I don't care whether it is there or not. When I use it, I define a particular instance (double, a constant formal series, a constant element of some differential algebra I enjoy personally, etc. No default would help me anyway). And then, I give it the type it deserves.

Evidently you use pi in more 'serious' programs than I do. I use pi simply for geometric reasons, when I wish to specify circular or elliptic paths or similar constructions. For this I am pleased that the language libraries give me pi, because they save me the work of defining it.

...

Given that pi is often used with sin, as in "sin (t * pi)" it would seem very odd if pi forced that to be monomorphic:

Oh yes, everybody in the world uses in ONE program several overloaded versions of pi, of the sine function, etc. Well, perhaps not everybody, for example I don't. And I use numerics quite often.

I like to write a complex function which might use multiple trig functions and pi, to describe the kind of thing about. I might want to use that function at Double, or GLdouble, or GLfloat, for various reasons. I don't particularly want to have to think about that kind of thing more than I have to.

How often *you* needed simultaneously overloaded pi and trigs in such a way that a default could help you? Answer sincerely (if you wish to answer at all...)

The default wouldn't help me at all. The default would help a (putative) designer of a new Floating instance, and I have never been one of those. If it is true of many Floating instances that (atan 1 * 4) is an accurate way to calculate pi (and it appears to be 'accurate enough' for Float and Double, on my computer) then adding it as a default doesn't appear to do any harm. I can't say I think it's very important either. Jules

Dan Piponi writes:

Jules Bean said:

...

If it is true of many Floating instances that (atan 1 * 4) is an accurate way to calculate pi (and it appears to be 'accurate enough' for Float and Double, on my computer) then adding it as a default doesn't appear to do any harm.

... For the case of power series as an instance of Num, using 4*atan 1 gives me the wrong thing as it triggers an infinite summation, whereas I'd want pi to simply equal the constant power series. Now you could counter that by saying that power series are an esoteric case. But apart from code in the libraries, most code I've seen that provides an instance of Num is doing something mildly esoteric.

For me series are not esoteric. But they can be implemented in a more cautious way, my own package behaves rationally: Prelude> :l Series [1 of 1] Compiling Series ( Series.hs, interpreted ) -- .... nasty messages omitted. Ok, modules loaded: Series. *Series> 4*atan 1 3.141592653589793 *Series> 4*atan 1 :: Series Double Loading package haskell98 ... linking ... done. [3.141592653589793,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0, ...] *Series> pi 3.141592653589793 *Series> pi :: Series Double [3.141592653589793,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0, ...] *Series> The implementation is, with (:-) as the cons-series operator, colon-dash for those whose browsers will convert it to some nice smiley...: zeros = 0:-zeros ... instance Floating a => Floating (Series a) where pi = pi:-zeros ... atan u@(u0:-_) = sInt (atan u0) (sDif u / (1+u*u)) etc. Of course, sDif differentiates and sInt integrates the series, see 2nd volume of Knuth for the algorithms, and papers, either a nice tutorial of Doug McIlroy, or my old paper for the implementation. The instance does it all. Default *could* help, and would give the same answer, but it would be much slower, so I would override it anyway. Jerzy Karczmarczuk

On 11 Oct 2007, at 4:49 am, Dan Piponi wrote:

Maybe this is the wrong point of view, but I think of defaults as impementations that are meant to be correct, but not necessarily the best way of doing things, leaving you the option to provide something better.

The example of tanh in the report (page 106) shows that this view cannot be sustained. As an algorithm for computing tanh, it cannot be defended, producing NaN in a vast range of cases where 1.0 is the easily obtained correct answer.

For the case of power series as an instance of Num, using 4*atan 1 gives me the wrong thing as it triggers an infinite summation, whereas I'd want pi to simply equal the constant power series.

So if you have a default for pi in Float, you still have to provide your own definition for power series. Without a default for pi, you have to provide your own definition for power series. It doesn't sound as though providing a default makes anything worse. One alternative would of course be to simply provide a definition with say 64 digits, to be rounded as appropriate by the compiler. That would be as accurate as 4*atan 1 for Float, Double, and Complex based on them, even for 128-bit floats.

On Wed, 2007-10-10 at 10:40 +0200, jerzy.karczmarczuk@info.unicaen.fr wrote:

Yitzchak Gale writes:

...

Dan Piponi wrote:

...

The reusability of Num varies inversely with how many assumptions you make about it.

A default implementation of pi would only increase usability, not decrease it.

Suppose I believe you. (Actually, I am afraid, I have doubts.) Can you provide some examples of this "increased usability"?

If possible, with a *relevant* context, which shows that PI should belong by default to the class Floating (whatever we mean by that...)

pi /is/ a method of class Floating. It just doesn't have a default implementation. jcc

On Thu, 2007-10-11 at 02:11 +0200, jerzy.karczmarczuk@info.unicaen.fr wrote:

Jonathan Cast adds 'something' to a discussion about pi.

I commented the statement of Yitzchak Gale, who answered some point of Dan Piponi:

...

...

...

A default implementation of pi would only increase usability, not decrease it.

I said:

...

...

Can you provide some examples of this "increased usability"?

If possible, with a *relevant* context, which shows that PI should belong by default to the class Floating (whatever we mean by that...)

pi /is/ a method of class Floating. It just doesn't have a default implementation.

Now, do you have anything to propose, or you just want to criticise my wording?

Yes. I am very eager to criticize your wording. To wit, I'm still failing to understand what your position is. Is it fair to say that your answer to my question, why pi has no default implementation, is `in fact, pi shouldn't be a method of Floating anyway'? If not, I can only beg for a precise, careful statement of exactly what it is you are arguing for. Btw: I am arguing that I (still) don't understand why the line pi = acos (-1) or something like it doesn't appear at an appropriate point in the Standard Prelude, given that the line pi :: a appears nearby said point. I am eager to be enlightened. But I haven't been, yet. jcc

Just goofing around with arrows and foldr while reading Hutton's excellent paper on folds (http://www.cs.nott.ac.uk/~gmh/fold.pdf). Wondering if this can be done automatically and more generally? module Main where import Control.Arrow import Data.List -- sum and length expressed as foldr. fsum = foldr (\n -> (+n)) 0 flen = foldr (\n -> (+1)) 0 -- compute average using arrows.. -- compute the sum of a list, compute the length, and do a divide. -- this traverses the list twice using two foldrs. avg1 = uncurry (/) . (fsum &&& flen) avg2 = uncurry (/) . (foldr (\n -> (+n)) 0 &&& foldr (\n -> (+1)) 0) -- But the two foldr's can be fused together -- here we're mixing the two foldr constants 0 and 0 to (0,0) -- and we're mixing the two functions (\n -> (+n)) and -- (\n -> (+1)) to (\n -> (+n) *** (+1)). avg3 = uncurry (/) . foldr (\n -> (+n) *** (+1)) (0, 0) main = do print $ avg1 [1,2,3,4] print $ avg2 [1,2,3,4] print $ avg3 [1,2,3,4] Tim Newsham http://www.thenewsh.com/~newsham/

Sorry for reacting so late on this mail. I'm digging through some old mails... On 10/12/07, Dan Weston wrote:

Always check optimizations to make sure they are not pessimizations!

Actually, traversing the list twice is very cheap compared to space leakage, and accumulating pairs requires tuple boxing and unboxing which I don't know how to get GHC not to do.

I agree hole-heartedly that replacing multiple traversals with a single traversal should be done with care as it more often than not results in a pessimization. Indeed you showed just that with your examples! But I'd thought it'd be interesting to see how it can actually be an improvement if done carefully. \begin{code} import Control.Arrow import qualified Data.Strict.Tuple as T import Data.Strict.Tuple (Pair(..)) import Control.Parallel avg4 = uncurry (/) . (foldl' (+) 0 &&& foldl' (\x y -> x + 1) 0) avgS = T.uncurry (/) . foldl' (\p n -> ((+n) *!* (+1)) p) (0 :!: 0) avgP = uncurry (/) . (foldl' (+) 0 &!& foldl' (\x y -> x + 1) 0) (*!*) f g (a :!: b) = f a :!: g b (&!&) f g a = fa `par` (fa,ga) where fa = f a ga = g a \end{code} avg4 is the function which was best among Dan's benchmarks. avgS uses strict tuples. I just threw in avgP for fun, it traverses the lists in parallel. Note: I do have a dual core machine so it makes sense to try avgP. I fed these functions to ghc with the -O2 and -threaded flags and timed them using the list [1..10000000]. The result (best times out of several runs): avg4: 284 ms avgS: 184 ms avgP: 248 ms It seems doing a single traversal can be faster if your write your function carefully. Doing the traversal in parallel was beneficial but not as good as the single traversal. Cheers, /Josef

On 10/26/07, Dan Weston wrote:

Thanks for letting me know about the Data.Strict library on Hackage. I will definitely make use of that! BTW, you left out an import Data.List(foldl') in your example.

Yes, Data.Strict can be pretty handy for getting the right strictness. Sorry about the missing import.

My timing test is an order of magnitude worse than yours. Do you have an extra zero in your list endpoint?

...

I fed these functions to ghc with the -O2 and -threaded flags and timed them using the list [1..10000000]. The result (best times out of several runs): avg4: 284 ms avgS: 184 ms avgP: 248 ms

Using ghc -threaded -O2 --make Avg.hs for ghc 6.6.1, I ran your tests on [1..10000000] and got the user times:

avg4: 12.75 s avgS: 3.65 s avgP: 15.56 s

The funny thing is that avg4/avgS = 3.5 for and only 1.5 for you. I understand that with only 1 processor my avgP time may be twice yours, but not the avgS or avg4.

Oooops.. My numbers are totally bogus. I had code that looked like the following: \begin{code} main = do time avg4 [1..10000000] time avg4 [1..10000000] time avg4 [1..10000000] time avgS [1..10000000] time avgS [1..10000000] time avgS [1..10000000] time avgP [1..10000000] time avgP [1..10000000] time avgP [1..10000000] \end{code} Not very elegant I know but I thought it would do the job. Apparently I was wrong. GHC does common subexpression elimination on all the lists so they're all shared between the different calls. Of course, the first function call would always take long time but I ignored it, thinking it was some anomaly. Anyway, I was totally sure that GHC only did cse on constructor expressions and not on arbitrary computations. Guess I was wrong. A little searching revealed the following quote by Simon PJ:

GHC does a very simple form of CSE. If it sees let x = e in ....e.... it replaces the inner 'e' by x. But that's all at the moment.

Lesson learned. Less bogus timing: avg4: 18.0s avgS: 2.2s avgP: 17.4s OK, so these figures make an even stronger case for my conclusion :-) Single traversal can be much faster than multiple traversals *when done right*.

I have the following machine:

Main memory size: 2026 Mbytes Num Processors: 1 Processor Type: Intel(R) Xeon(TM) CPU 2.80GHz x32 Clock Speed: 2790 MHZ

In case you're still interested my machine looks like this: Memory: 2026 Mbytes Processor: AMD Turion(tm) 64 X2 Mobile Technology TL-56 Clock Speed: 1800MHz All the best, /Josef

On 10/28/07, Isaac Dupree wrote:

Josef Svenningsson wrote:

...

Less bogus timing: avg4: 18.0s avgS: 2.2s avgP: 17.4s

OK, so these figures make an even stronger case for my conclusion :-) Single traversal can be much faster than multiple traversals *when done right*.

Did you use +RTS -N2 on your program (or whatever it is that makes GHC actually use multiple threads? or is that not necessary?) Anyway I assume you wouldn't get better than 9.0s, which is still much worse than 2.2s.

Oh, this is getting embarrassing.. Indeed, I forgot to use +RTS -N2. But using those flags yielded a very interesting result: avgP: 4.3s Superlinear speedup!? As you say, I would have expected something slightly larger than 9s. I think what happens here is that for avg4 the entire list has to be kept in memory between the two traversals whereas for avgP the beginning of the list can be garbage collected incrementally as the two threads traverse it. This could mean that the list never moves to the second generation in the memory manager and that can maybe account for the additional time savings. I'm not sure how to verify that this is the case though. Cheers, /Josef

Hello Josef, Monday, October 29, 2007, 2:08:54 PM, you wrote:

...

that can maybe account for the additional time savings. I'm not sure how to verify that this is the case though.

Bulat kindly suggested I use +RTS -s to monitor the garbage collectors behavior. It seems my hypothesis was right.

you may also look at these data: 1,225,416 bytes allocated in the heap 152,984 bytes copied during GC (scavenged) 8,448 bytes copied during GC (not scavenged) 86,808 bytes maximum residency (1 sample(s)) 3 collections in generation 0 ( 0.00s) 1 collections in generation 1 ( 0.00s) if your hypothesis is true, amount of data copied and number of generation-1 collection should be much less in the second case -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Josef, Tuesday, October 30, 2007, 4:13:04 PM, you wrote:

201,080,832 bytes maximum residency (9 sample(s)) 1681 collections in generation 0 ( 1.67s) 9 collections in generation 1 ( 13.62s)

184,320 bytes maximum residency (2 sample(s)) 1908 collections in generation 0 ( 0.04s) 2 collections in generation 1 ( 0.00s)

Allocation is cheap, copying expensive.

not copying itself, but generation-1 garbage collections. while g-0 collection scans 256kb which lives in CPU cache, g-1 collection scans entire 100-200 mb of data that is very slow. try to use -H1g option, though :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

My last word (promise!) on the subject, especially addressed to Jonathan Cast, who writes:

To wit, I'm still failing to understand what your position is.

I quote the Master: Lennart:

Come on people! This discussion is absurd. The numeric classes in Haskell have a lot of choices that are somewhat arbitrary. Just live with it. If pi has a default or not has no practical consequences.

My position is: don't put rubbish into the Prelude! Swelling the standard environment with useless stuff has two consequences, it pollutes the name space, and slows down the learning process of the language, since many newbies will try to learn those useless quirks. So, no default, and no class membership. But, as LA says, we can live with, we have more important sorrows, all of us... Jerzy Karczmarczuk

On Wed, 10 Oct 2007, Yitzchak Gale wrote:

Dan Piponi wrote:

...

The reusability of Num varies inversely with how many assumptions you make about it.

A default implementation of pi would only increase usability, not decrease it.

As the others have shown, you can compute PI in many ways. Which one is appropriate for the general case? Do you have so much types that you want to make instances of Floating, that manually defining 'pi' annoys you? Not giving a default implementation can even improve code because people have to think about a good implementation rather than relying on the default one.