CODEWITHSUNDEEP
haskell
user2913694
user2913694

Reputation:

Haskell 'count occurrences' function

I implemented a count function in Haskell and I am wondering will this behave badly on large lists : 

count   :: Eq a => a -> [a] -> Int
count x =  length . filter (==x)

I believe the length function runs in linear time, is this correct?

Edit: Refactor suggested by @Higemaru

Upvotes: 17

Views: 49135

Answers (3)

Higemaru
Higemaru

Reputation: 364

I think you can make it slightly shorter

count :: Eq a => a -> [a] -> Int
count x = length . filter (x==)

(I would have written a (lowly) comment if I could)

Upvotes: 9

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68172

Length runs in linear time to the size of the list, yes.

Normally, you would be worried that your code had to take two passes through the list: first one to filter and then one to count the length of the resulting list. However, I believe this does not happen here because filter is not strict on the structure of the list. Instead, the length function forces the elements of the filtered list as it goes along, doing the actual count in one pass.

Upvotes: 12

bheklilr
bheklilr

Reputation: 54078

That really depends on the list. For a normal, lazily evaluated list of Ints on my computer, I see this function running in about 2 seconds for 10^9 elements, 0.2 seconds for 10^8, and 0.3 seconds for 10^7, so it appears to run in linear time. You can check this yourself by passing the flags +RTS -s -RTS to your executable when running it from the command line.

I also tried running it with more cores, but it doesn't seem to do anything but increase the memory usage a bit.

An added bonus of the lazy computation is that you only make a single pass over the list. filter and length get turned into a single loop by the compiler (with optimizations turned on), so you save memory and efficiency.

Upvotes: 1

Related Questions