CodeAbbey #21 Array Counters

Question

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

Answer 1

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

Answer 2

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

Answer 3

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 Control.Monad.ST
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.