[Haskell-cafe] Efficiency Question

[Daniel Fischer]

Hi folks,

toying a bit with splitAt and take, I have met yet another thing, I don't 
understand.
In the Hugs Prelude, splitAt is defined

splitAt n xs | n <= 0 = ( [],xs)
splitAt _ []               = ([],[])
splitAt n (x:xs)        = (x:xs',xs'') where (xs',xs'') = splitAt (n-1) xs

whereas in the report it is described as (take n xs,drop n xs) -- I have no 
problem with that, since the report explicitely states that the functions 
need not be implemented as given there --, let's call that function bSplit (b 
was chosen for 'bad').

Now, as expected, splitAt takes fewer reductions than bSplit, splitAt (n+1) 
takes 18 reductions more than splitAt n, bSplit (n+1) takes 32 more than 
bSplit n (24 for take, 8 for drop).
So far so good, now changing to ghci and testing that on a long list 
([1 .. 1000000], [1 .. 500000]), splitting at half, then printing the two 
middle numbers. The first surprise was that there bSplit was faster than 
splitAt (roughly twice as fast).

Does anybody know how that can be??

The second surprise was the variation of time needed.
For the longer list, splitAt usually took 0.45 - 0.48 secs, occasionally about 
0.9 secs (I think that will be due to gc),
bSplit usually took 0.22 - 0.25 secs, occasionally about 0.7 secs (gc, 
probably).
For the shorter list, splitAt took 0.22 - 0.28 secs (0.7 with gc), bSplit took 
0.10 - 0.20 secs (0.6 with gc).

Now, what's the explanation for that? 
Differences of, say, 0.03 secs or so I happily attribute to an occasional 
interrupt or something, but the difference between 0.10 and 0.20 I would like 
an explanation for.

Another thing, while toying, I found out that a comparison (n <= 0) takes 
three reductions more than (n < 1) according to my hugs, so changing the 
definition of splitAt thus, we require (3*n) reductions less. But the number 
of reductions and speed are different things, as witnessed by the above, so 
would it be an improvement to replace "n <= Integerliteral"-queries by 
"n < Integerliteral"-queries or doesn't that make any difference at all in 
execution time?

Finally, in several contexts I needed to cons an element to one of a pair of 
lists, so I defined

infixr 5 &,§

(&) :: a -> ([a],[b]) -> ([a],[b])
x & (xs,ys) = (x:xs,ys)

(§) :: b -> ([a],[b]) -> ([a],[b])
y § (xs,ys) = (xs,y:ys).

I find them useful (though I don't like the symbols, if you have any better 
ideas, thx) and for splitAt, (&) saves another reduction per step.

Now, I would like to have such operators supplied by the language, so is there 
space for them in the Prelude or in List, or does hardly anyone besides me 
ever need them?

Have a wonderful weekend ye all,
Daniel