- Haskell-Cafe - Haskell.org

How to compare the time-efficiency of Haskell functions?
by Dimitre Novatchev 18 Oct '01

18 Oct '01

Dear Haskell programmers, I am a complete newbie and just wrote and tested my first few Haskell functions using Hugs98. I have (just copied) the quicksort function and I wrote another one -- dvcSort, which stands for "Divide and Conquer Sort". It seems that dvcSort runs much faster in the quicksort worst case and I wanted to provide more exact timing comparison b/n the two implementations based on various input lists. The first and relatively minor problem is that it seems there's no time library in Hugs. The real reason I'm asking for help is that I don't know what exactly means to "time a function" in Haskell. If you thought about the laziness of the language, then you're right. In my concrete case quicksort outputs the first list element (I use [-10000..10000]) almost immediately, then outputs the next number with a speed approximately one per second. From the code of quicksort it is straightforward to see, that in this case every element from left to right is compared with all the rest, and being the minimal, it can be immediately output. In this case quicksort performs like finding all the minimums and outputting them, and this has an O(N^2) complexity. Therefore, it would be incorrect to state that the time for executing quicksort is the time for its producing the first element of the result list. On the other side, based on analysis of dvcSort, it can be concluded that when it produces the first element of the result, then it has already calculated all elements of the sorted list. The time it takes to output 20001 numbers also affects the correctness and credibility of any timing. I had to use a trick like this: resSort :: (Ord a) => ([a] -> [a]) -> [a] -> (a, a) resSort f xs = let z = f(xs) in (z!!0, (last z)) and I'm timing (resSort quicksort) and (resSort dvcSort) now. However, this is a trick, based on intuition and on my knowledge of these two algorithms -- the same trick is not likely to be universally applicable and useful. My question is: Is there a better and general approach for timing Haskell functions? Any thoughts and recommendations will be invaluable for me. Thanking you in advance, Cheers, Dimitre Novatchev. __________________________________________________ Do You Yahoo!? Make a great connection at Yahoo! Personals. http://personals.yahoo.com

1 0

Support for SOAP, Xml Schema?
by Siegfried Klein 18 Oct '01

18 Oct '01

Are there any haskell modules available for SOAP or Xml Schema (instead or in addition to DTD)? -- Thanks in advance Siegfried

1 0

please add me
by lo janus 17 Oct '01

17 Oct '01

me(a)lojanus.com

1 0

(no subject)
by Nuno Carvalho 17 Oct '01

17 Oct '01

subscribe

1 0

Newbie question about classes and class parameters
by Dmitry Astapov 17 Oct '01

17 Oct '01

Let's say we have infamous Set class defined this way: > class Set s a where > empty :: s a > isEmpty :: s a -> Bool Lets also say that we could define sets as lists: > data SetAsList a = SL [a] deriving (Eq,Ord,Show) > instance Set SetAsList a where > empty = SL [] > isEmpty (SL []) = True > isEmpty _ = False So far, so good. Lets define type synonim for set of integers: > type IntegerSet = SetAsList Integer And set of sets of integers: > data IntegerSuperSet = ISS (SetAsList IntegerSet) Testing in Hugs show that everything seems to be working: Main> :t ISS (SL [ (SL [1,2,3])::IntegerSet, (SL [4,5,6])::IntegerSet ]) ISS (SL [SL [1,2,3],SL [4,5,6]]) :: IntegerSuperSet However: Main> isEmpty (ISS (SL [(SL [1,2,3])::IntegerSet, (SL [4,5,6])::IntegerSet])) ERROR - Type error in application *** Expression : isEmpty (ISS (SL [SL [1,2,3],SL [4,5,6]])) *** Term : ISS (SL [SL [1,2,3],SL [4,5,6]]) *** Type : IntegerSuperSet *** Does not match : a b This is completely understood - I need to state that IntegerSuperSet is an instance of Set for isEmpty to be working. But: > instance Set IntegerSuperSet where > empty = ISS (SL []) > isEmpty (ISS (SL [])) = True > isEmpty _ = False gives me: Reading file "/tmp/bug.lhs": ERROR /tmp/bug.lhs:38 - Wrong number of arguments for class "Set" Obviously I am missing something very important here. Could someone enlighten me? -- Dmitry Astapov //ADEpt E-mail: adept(a)umc.com.ua Information Systems Expert Office: +380-50-110-3876 Ukrainian Mobile Communications Mobile: +380-50-330-2019 GPG KeyID/fprint: F5D7639D/CA36 E6C4 815D 434D 0498 2B08 7867 4860 F5D7 639D

2 1

Re: Haskell 98 - Standard Prelude - Floating Class
by Dylan Thurston 16 Oct '01

16 Oct '01

On Mon, Oct 15, 2001 at 03:52:06PM +0200, Kent Karlsson wrote: > > Simon Peyton-Jones: > > > Russell O'Connor suggests: > > > | but sinh and cosh can easily be defined in terms of exp > > > | sinh x = (exp(x) - exp(-x))/2 > > > | cosh x = (exp(x) + exp(-x))/2 ... > > > This looks pretty reasonable to me. We should have default methods > > > for anything we can. > Mathematically, yes. Numerically, no. Even if 'exp' is implemented > with high accuracy, the suggested defaults may return a very > inaccurate (in ulps) result. Take sinh near zero. sinh(x) with x > very close to 0 should return x. With the above 'default' sinh(x) > will return exactly 0 for a relatively wide interval around 0, which > is the wrong result except for 0 itself. Hmm, on these grounds the current default definition for tanh x is even worse behaved: tanh x = sinh x / cosh x For moderately large floating point x, this will overflow. Frankly, I don't think the whole discussion matters very much; nobody who cares will use the default definitions. But remember to think about branch cuts. And why not go further? cos x = (exp (i*x) + exp (-i*x))/2 where i = sqrt (-1) etc. > In general, this is why LIA-2 (Language Independent Arithmetic, part > 2, "Elementary numerical functions", ISO/IEC 10967-2:2001) rarely > attempts to define one numerical operation in terms of other > numerical operations. That is done only when the relationship is > exact (even if the operations themselves are inexact). That is not > the case for the abovementioned operations. But it is the case for > the relationship between the complex sin operation and the complex > sinh operation, for instance. (Complex will be covered by LIA-3.) This sounds like a very interesting standard. I am constantly annoyed by ISO's attempts to hide their standards; one might wonder what the purpose is of having unavailable "standards". Is the content available somewhere? Best, Dylan Thurston

4 3

ExitFailure 127
by Sebastian Schulz 16 Oct '01

16 Oct '01

hi. I'm trying to run an system command (wget) within a CGI script and get the following error: >Exitfailure 127 How can I get more information out of an ExitFailure x error? Can I use ioeGetErrorString? But this function doesn't work on ExitCode, which system returns. TIA sebastian

1 0

fixed point
by Song Li 15 Oct '01

15 Oct '01

Hi, anybody can explain how Y combinator work in find fixed point ? say : Y = 'lam' f . ('lam' x . f(xx))('lam' x . f(xx)) X = Y F -> ( 'lam' x .F(xx))('lam' x . F(xx)) -> F(('lam' x . F(xx))('lam' x . F(xx))) <- How can this expression be derived ???????????? ->F X <- And why ? Thanks a lot! Song

1 0

a newbie's question
by Song Li 14 Oct '01

14 Oct '01

Hi, there, Could anybody explain what does this type defination mean : data xxx a = xxx (a ->b) looks xxx can use itself as constructor(like tree) but change the type...... Thanks! Song

2 1

Closed Classes
by Eric Allen Wohlstadter 12 Oct '01

12 Oct '01

Are there any plans to add closed classes as a hugs extension? This was described in the paper: Object-Oriented Style Overloading for Haskell, Mark Shields and Simon Peyton Jones; BABEL workshop '01. Eric Wohlstadter

1 0