Thanks for the advice. After taking most of it it is faster. But it is still many times slower than it ought to be! This algorithm should be much faster than simply sorting the list, and yet it is more than twice as slow!

One note, you said:
""""
> Increment length.
>
>> modifySTRef
>> lengthRef
>> (+1)

This will create a big thunk for the length, you should use

oldLength <- readSTRef lengthRef
writeSTRef lengthRef $! oldLength + 1

(I'm not sure if a strict modifySTRef exists somewhere...)""""

Actually, replacing modifySTRef with that code is just a hair slower... Not sure why.

I'm attaching the super optimized version. Along with the profiler output. I just can't understand what is slow here :(

Timothy

---------- Původní zpráva ----------
Od: Felipe Almeida Lessa <felipe.lessa@gmail.com>
Datum: 3. 9. 2012
Předmět: Re: [Haskell-cafe] hstats median algorithm

On Mon, Sep 3, 2012 at 11:18 AM, Felipe Almeida Lessa
<felipe.lessa@gmail.com> wrote:
> Ditto for oldLen here. Also, you can simplify this lambda a lot:
>
> import Control.Applicative ((<$>))
>
> \(oldLen, oldVal) ->
> let newLen = oldLen + 1
> newVal = (number:) <$> oldVal
> in newLen `seq` newVal `seq` (newLen, newVal)

Or, using BangPatterns,

\(oldLen, oldVal) ->
let !newLen = oldLen + 1
!newVal = (number:) <$> oldVal
in (newLen, newVal)

Cheers,

--
Felipe.