2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Gurkenglas Aug 14 '16 at 8:33
  • \$\begingroup\$ 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? \$\endgroup\$ – R B Aug 14 '16 at 9:35
  • \$\begingroup\$ Well you can ask lambdabot: ircbrowse.net/browse/… or did you disagree on something else than (+) on Int being strict in both arguments? \$\endgroup\$ – Gurkenglas Aug 14 '16 at 10:03
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.