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 -> 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 > 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.