Simple problem.
Given a String, I want to be able to enter a letter and then have my function count the number of times that letter appears in a string.
countLetters :: String -> Char -> Int
How can this be done?
Add a comment
|
2 Answers
With
countLetters :: String -> Char -> Int
countLetters str c = length $ filter (== c) str
This gets only the characters in str that equal c, then computes the length of that.
2 Comments
user2407038
This suffers the performance penalty of having to traverse the entire input string once to filter, and then traverse the result of that to get the length.
bheklilr
But aren't
length and filter both lazy functions? I would imagine that GHC could optimize a simple case like that to produce a single loop.That depends on the number of calls you'd like to make to one String. Simple solution would be to just read every character in the string, if it matches the one you're looking for, increase the counter.
Now, if you're mapping over something with a counter, you can obviously use fold:
countLetters xs x = foldl (\count char -> if char == x then (count + 1) else count) 0 xs
However, if you want to do many queries, it makes more sense to build the lookup table (i.e. sort) first. Then you can get the number of repetitions of arbitrary character in O(1) (the whole algorithm is still O(n)).
answered Oct 10, 2013 at 13:30
Bartek Banachewicz
39.5k8 gold badges100 silver badges141 bronze badges
2 Comments
Bartek Banachewicz
Assuming you're using a fixed-range fixed-size table, extraction of a value is
O(1). Think raw memory access and pointer arithmetic, for example.