Geek Answers Handbook

Haskell counter function

I have implemented the count function in Haskell, and I am wondering if this will work badly on large lists:

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

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

Edit: Reactor proposed by @Higemaru

+7
haskell
source share
3 answers

Length runs in linear time to list size, yes.

Usually, you fear that your code would have to go through two passes in the list: first one to filter, and then one to calculate the length of the resulting list. However, I believe that this does not happen, because the filter is not strict in the list structure. Instead, the length function causes the items in the filtered list to move, making the actual count in one go.

+9
source share

I think you can make it a little shorter

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

(I would write a (humble) comment if I could)

+3
source share

It really depends on the list. For a normal, lazily priced Int list on my computer, I see that this function works after about 2 seconds for 10 ^ 9 items, 0.2 seconds for 10 ^ 8 and 0.3 seconds for 10 ^ 7, so it seems to be runs in linear time. You can verify this yourself by passing the +RTS -s -RTS to your executable file when launched from the command line.

I also tried to run it with a lot of cores, but it does not seem to do anything, but slightly increases memory usage.

The added bonus of lazy computing is that you only make one pass through the list. filter and length turn into a single cycle by the compiler (with optimization turned on), so you save memory and efficiency.

0
source share

More articles:


All Articles