# CodeAbbey #21 Array Counters

I'm trying to learn some Haskell by working my way through the CodeAbbey problems. I really struggled to find a nice functional (but still efficient) way to solve problem #21: Array Counters.

The problem is, given a list of M numbers between 1 and N (an input parameter), to count the number of occurrences of each number. The question strongly suggests the imperative approach of using an array of counters and incrementing the counter at the relevant index.

Example:

Input:
10 3
3 2 1 2 3 1 1 1 1 3

Expected output:
5 2 3


My code:

count :: Int -> [Int] -> [Int]
count n = go (replicate n 0)
where
go cs []       = cs
go cs (x : xs) = go (incList x cs) xs

incList :: Int -> [Int] -> [Int]
incList x cs = (take (x - 1) cs) ++ [cs!!(x - 1) + 1] ++ (drop x cs)

main :: IO ()
main = do line <- getLine
let [m, n] = map (read :: String -> Int) $words line line <- getLine let list = map (read :: String -> Int)$ words line
putStrLn $unwords$ map show $count n list  ## 3 Answers You could use a Map, from the Data.Map module to count occurrences of the numbers: import qualified Data.Map.Strict as M count :: [Int] -> M.Map Int Int count xs = M.fromListWith (+)$ zip xs (repeat 1)


This way you only iterate once through the list of pairs (number, 1) and sum the 1s of each different number.

Since we don't have mutation in Haskell, you can often use a Map as a replacement for a dictionary in imperative languages (or arrays).

If an array is what you need, use an Array! This solution to this problem is even given in the linked docs, because you're actually just creating a histogram.

hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]

count n xs = hist (1, n) xs


One subtlety is that you should probably use a strict version of (+) to avoid building up a long chain of thunks.

{-# LANGUAGE BangPatterns #-}

plus :: Num a => a -> a -> a
plus !a !b = a + b

• Your plus should not change anything about building up of thunks, right? (+) on Ints is already strict. "If the accumulating function is strict, then accumArray is strict in the values, as well as the indices, in the association list." from those same docs says we're safe. – Gurkenglas Aug 14 '16 at 8:33
• I don't believe that's true, but it could very well depend on optimization settings or have changed in some recent (to me) GHC version. Do you have a cite? – R B Aug 14 '16 at 9:35
• Well you can ask lambdabot: ircbrowse.net/browse/… or did you disagree on something else than (+) on Int being strict in both arguments? – Gurkenglas Aug 14 '16 at 10:03

In addition to the other answers: If you want to have fast, imperative solution in Haskell, the way to go would be the [ST monad]. You can use STArray or even STUArray (unboxed, which means it's strict and memory efficient - no thunks):

import Control.Monad (forM_)
import Data.Array.ST
import Data.Array.Unboxed (UArray)

count :: (Int, Int) -> [Int] -> UArray Int Int
count b@(l, h) xs = runSTUArray $do arr <- newArray b 0 forM_ xs$ \x -> readArray arr x >>= writeArray arr x . (+ 1)
return arr


This returns a pure result, but works somewhat more efficiently than Map (which is otherwise the way to go in Haskell), at the expense of being more imperative.

On the other side of the spectrum, a way how to look at the problem is how to construct the simplest histogram - from a single value, and then how to combine histograms together. A one-element histogram (represented as Map a Int) is singleton x 1 and they can be combined together by combining maps with unionWith (here generalized to arbitrary values that can be ordered):

import qualified Data.Map as M

count :: (Ord a) => [a] -> M.Map a Int
count = M.unionsWith (+) . map (\x -> M.singleton x 1)


If you want to go even further in this direction, you can realize that distributions are monoids:

import qualified Data.Map as M

newtype Distribution a = Distribution { getDistribution :: M.Map a Int }
deriving (Show, Read, Eq, Ord)

instance (Ord a) => Monoid (Distribution a) where
mempty = Distribution M.empty
mappend (Distribution m1) (Distribution m2) = Distribution $M.unionWith (+) m1 m2 singleton :: (Ord a) => a -> Distribution a singleton x = Distribution$ M.singleton x 1

count :: (Ord a) => [a] -> Distribution a
count = foldMap singleton


It's somewhat more verbose, but separates the general properties of distributions (the Monoid instance) from the final computation, which then becomes trivial. Another advantage is that the newtype allows to hide the internal representation, which can be potentially replaced by something else, while keeping the interface intact.