How to compare the time-efficiency of Haskell functions?

[Dimitre Novatchev]

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