HackerRank: Counting Sort 1

I've just solved this challenge, though I feel that there is a problem with stack growth or something because the 5th testcase has a runtime error

import Control.Monad
import Data.Sequence hiding (replicateM, replicate, take, drop)
import Data.List

main :: IO ()
main = do n  [Int] -> [Int]
calc [] y      = y
calc (x:xs) ys = calc xs ((take (x) ys) ++ ((ys!!x) + 1):(drop (x+1) ys))

I feel that there should be a much neater solution, which doesn't cause an overflow as this is quite messy.

It would be nice to get everyone's thoughts on more efficient/nicer solutions

Let's imagine this problem as building a histogram. We draw out an X axis of 100 (0 count :: [Int] -> Array Int Int
count input = _


The best way to build an array is to ... uh ... I never remember. So we consult the docs, specifically the array construction section. There's a function here called accumArray that folds over a list of (index, value) tuples – that is, it walks each tuple and uses it to accumulate into a value into the array that is returned back to us. In our case, each tuple will be (number, 1): we'll have it so that each tuple represents a single count of the number. Our job is then to convert a bunch of tuples like this

(2, 1) (5, 1) (5, 1) (3, 1)


to a histogram like this

0: 0
1: 0
2: 1
3: 1
4: 0
5: 2


Back to our code:

count :: [Int] -> Array Int Int
count input = accumArray _ _ (0, 99) (zip input (repeat 1))


The trick here is that repeat 1 is an infinite array, but we know input is finite and zip terminates when either argument terminates.

It remains to specify the accumulating function, which takes two arguments (the frequency of the number thus far and then second value of our tuple, which is always the number 1) and is supposed to return the new frequency. This is as simple as incrementing the old number, or just adding one.

count :: [Int] -> Array Int Int
count input = accumArray (\old one -> old + one) _ (0, 99) (zip input (repeat 1))


This being Haskell, we can simplify this to

count :: [Int] -> Array Int Int
count input = accumArray (+) _ (0, 99) (zip input (repeat 1))


For the greater good. And we're done! Oh, and we need to specify a default frequency for values that we didn't encounter in the list. For us, that's a simple zero.

Combining this with your IO code that reads from stdin, we get:

import Data.Array
import Data.List

main :: IO ()
main = do
_ Array Int Int
count input =
accumArray (+) 0 (0, 99) (zip input (repeat 1))


And if we wanted to be a smart-ass we could golf the solution into a one-liner:

import Data.Array
import Data.List

main :: IO ()
main = getLine >> getLine >>= (putStr . unwords . map show . elems . accumArray (+) 0 (0, 99) . flip zip (repeat 1) . map read . words)


I think that last line even fits into a tweet.

StackExchange Code Review Q#112621, answer score: 7