Let's imagine this problem as building a histogram. We draw out an X axis of 100 (0 <= x < 100, as given by the problem). For each element that we're given, we move the bar up by one in the histogram.
For something like this we have Data.Array
. We can build an Array Int Frequency
that will map each number to the frequency of the number. Each insertion into the array will be O(1)
. Initializing the array will also be O(1)
since the size of the array is fixed. We'll just have the computer set aside 100 slots of memory for us up top, every time. This should lead to a running time of initialization + n * insertion = O(n)
, which indeed beats O(n lg n)
.
Our function will have this type:
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
_ <- getLine
numbers <- getLine
(putStr . unwords . map show . elems . count . map read . words) numbers
count :: [Int] -> 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.