Search for the sequence "Count"
Given a list of integers xs
, let's say:
count :: [Integer] -> Integer -> Integer
count xs n = length . filter (==n) $ xs
count the number of times an integer n
occurs in the list.
Now given a "list" (some kind of array of integers, maybe something like List) of length n
, write a function
countSequence :: [Integer] -> Integer -> Integer -> Integer
countSequence xs n m = [count xs x | x <- [0..m]]
which outputs a "count list" (0th index contains the number of times 0 in the list, 1st index contains the number of times 1 in the list, etc.) which has a time-time o (m * n)
The above implementation I gave has O (m * n) complexity. In Python (which I'm more familiar with), this is easy to do in O (m + n) time --- iterating over a list, and each item increments a counter in another list that is initialized to all zeros and length (m + 1).
How can I get a better implementation in Haskell? I would prefer it if it weren't some trivial way to implement a Python solution (for example, add another input to the function to store a "list of counters" and then through it).
source to share
In O(n+m)
(sort of, I think maybe):
import Data.Ix (inRange)
import qualified Data.IntMap.Strict as IM
countSequence m =
foldl' count IM.empty . filter (inRange (0,m))
where count a b = IM.insertWith (+) b 1 a
gives
> countSequence 2 [1,2,3,1,2,-1]
fromList [(1,2),(2,2)]
I didn't use n
it because you didn't use it either n
, and I'm not sure what it should be. I also moved the list to the last argument to put it in position to shrink it.
source to share
I think you should use your Python intuition - iterate over one list and increment the counter in another list. Here's an implementation with O (n + m) runtime:
import Data.Array
countSequence xs m = accumArray (+) 0 (0,m) [(x, 1) | x <- xs, inRange (0,m) x]
(This use case is even a motivating example of existence accumArray
in the documentation!) In ghci:
> countSequence ([1..5] ++ [1,3..5] ++ [1,4..5] ++ [1,5]) 3
array (0,3) [(0,0),(1,4),(2,1),(3,2)]
source to share
I imagine using it Data.IntMap
would be as efficient as it would for this job. One pass foldr
is performed to set IntMap
( cm
) and map
to build a new list containing the element counts at the respective positions.
import qualified Data.IntMap.Lazy as IM
countSequence :: [Int] -> [Int]
countSequence xs = map (\x -> let cm = foldr (\x m -> IM.alter (\mx -> if mx == Nothing then Just 1 else fmap (+1) mx) x m) IM.empty xs
in IM.findWithDefault 0 x cm) xs
*Main> countSequence [1,2,5,1,3,7,8,5,6,4,1,2,3,7,9,3,4,8]
[3,2,2,3,3,2,2,2,1,2,3,2,3,2,1,3,2,2]
*Main> countSequence [4,5,4]
[2,1,2]
*Main> *Main> countSequence [9,8,7,6,5]
[1,1,1,1,1]
source to share