Bucket sort in Haskell As a first step in learning Haskell I am solving this problem, which involves finding the Rith-ranked numbers, given some input list and many Ri. In an imperative language I would make a zeroed array c of length 200, increment c[h] for each height h, compute cumulative sums of c and then binary search c to determine the height corresponding to each given index. Because max_height is fixed, this has runtime linear in the size of input and bounded memory(*) excluding the input.
Here's my Haskell code:
max_height = 200
count_eq e = foldl (\c f -&gt; if e == f then c + 1 else c) 0
counts heights = map (flip count_eq heights) [0..max_height]
first_gt e l = f l 0 where f (x:xs) i = if x &gt; e then i else f xs (i+1)
solve heights indices = let accum = scanl1 (+) (counts heights) in
  map (flip first_gt accum) (map (subtract 1) indices)

It is correct but slow. I would like to know how to (A) reason about and (B) improve the performance. Also (C) can I achieve the same asymptotic performance as the imperative code?
(*) assuming each c[i] fits in a machine int. I believe the runtime statement holds regardless.
Lists are not for random access. As far as I know, Vectors are the modern way to have fixed-length random-access listlikes. They will allow you to do the traversing updates you want in one pass.

import qualified Data.Vector as V
counts = V.toList . V.accum (+) (V.replicate 200 0) . map (,1)


first_gt doesn't need a manual implementation:

import Safe
first_gt e = findIndexJust (&gt; e)


And just for fun, this should only traverse the counts result once. (Requires that indices is sorted, though.)

import Control.Monad.Trans.State
solve heights = scanl1 (+) . map length . splitsOnFoo . map (subtract 1) where
  splitsOnFoo = evalState $ traverse (state . span . (&lt;)) $ scanl1 (+) $ counts heights