To my
| It looks like List.partition
| is a stack eater in GHC-4.04.
| And this can be improved easily.
| Probably, there are many other stack or heap eaters.
| What the implementors think of this?
Simon Peyton-Jones <[EMAIL PROTECTED]> writes
> As various people have said, one can turn non-tail-recursive functions
> into tail-recursive ones, using an accumulating parameter.
>
> But this isn't obviously a win. Stack usage is decreased, but heap
> usage is increased by the same amount. It's not clear to me that
> the former is better than the latter (GHC, at least, grows its stack
> dynamically, and Hugs will too once we've completed the GHC/Hugs
> integration).
>
> I'm not sure how partition could be made much more efficient
> without also making it stricter.
I tried
----------------------------
pt p = prt [] []
where prt xs ys [] = (reverse xs, reverse ys)
prt xs ys (z:zs) = if p z then prt (z:xs) ys zs
else prt xs (z:ys) zs
main = let n = 123000 :: Int
(ys,zs) = pt (>0) [1..n]
in
putStr $ shows (last ys) "\n"
--------------------------------------
and found that it has
(time, minHeap, minStack) = (1.2 sec, 4700k, 1k )
against (0.9 , 4300, 1000)
of GHC- partition.
All right, probably, pt does not win.
> In general, though, we have not devoted a great deal of effort
> to performance-tuning the GHC prelude. If anyone finds a definition
> of a prelude function that out-performs the one that comes with
> GHC, please send it and we'll plug it in.
Well, minimum(By), maximum(By)
should run in constant heap+stack,
if programmed without foldl. For example,
minBy, maxBy :: Comparison a -> [a] -> a
-- example: compare -> [2,1,3,1] -> 1
-- (flip compare) -> [2,1,3,1] -> 3
minBy _ [] = error "minBy <comparison> []\n"
minBy cp xs = m xs
where m [x] = x
m (x:y:xs) = case cp x y of GT -> m (y:xs)
_ -> m (x:xs)
Here the type of the first argument differs from List.minimumBy,
but this can be improved easily.
Minor question: minimumBy could take the first argument
p asTypeOf min
or p asTypeOf compare - as in sortBy.
One could question, which is more usable.
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
