If we were writing this in an imperative language, it would look like (pseudo code)
int countBy(cond :: int -> bool, xs :: [int]) {
int cnt = 0;
foreach(x in xs) {
if (cond(x)) {
cnt += 1;
}
}
return cnt;
}
Clearly, we are going over every element in the list and adding 1
to cnt
if it meets the condition. If we wanted to, we could modify this somewhat to factor out the loop body (assuming this pseudo language has closures)
int countBy(cond :: int -> bool, xs :: [int]) {
int cnt = 0;
int body(int elem, int currentCnt) {
if (cond(elem)) {
return currentCnt + 1;
} else {
return currentCnt;
}
};
foreach(x in xs) {
cnt = body(x, cnt);
}
return cnt;
}
So we can see that our iteration is only dependent on our current value and the result obtained from the previous iteration. This kind of pattern is called a fold, and they can be elegantly represented in Haskell using the built-in fold*
functions. Usually, foldr
is a good choice, it's hard to go wrong with it. The type of foldr
is
foldr :: (x -> acc -> acc) -> acc -> [x] -> acc
I've purposely changed the type variables from what you'd see in GHCi to make it a bit more clear. The acc
type variable is for the accumulator. It is the value that is updated on each iteration. The x
is the type of the elements of your list. foldr
takes as its first argument a function that acts as your loop body. This function takes an element of the list and the accumulator and returns the next accumulator. foldr
then takes an initial accumulator value and finally a list to iterate over. We can write countBy
in Haskell as
countBy :: (a -> Bool) -> [a] -> Bool
countBy cond xs =
foldr -- Think of this as a for loop
body -- The body of our for loop
0 -- The initial value for cnt
xs -- The list to iterate over
where
body elem currentCnt =
if cond elem
then currentCnt + 1
else currentCnt
You could even in-line the body
to write
countBy cond =
foldr (
\x cnt ->
if cond x
then cnt + 1
else cnt
)
0
I also left off the xs
parameter for a more point-free style. Notice how this even looks almost like the original imperative style. You can of course make this more compact, and I certainly would. This can fit on one line without much trouble.
countBy cond = foldr (\x cnt -> if cond x then cnt + 1 else cnt) 0
Alternatively, if you wanted to write the recursion yourself, you only have to look at the definition of foldr
to figure out how:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f b [] = b
foldr f b (x:xs) = foldr f (f x b) xs
Here f
is our body
and b
is our accumulator. So if we follow this style:
countBy' :: (a -> Bool) -> Int -> [a] -> Int
countBy' cond cnt [] = cnt
countBy' cond cnt (x:xs)
| cond x = countBy' cond (cnt+1) xs
| otherwise = countBy' cond cnt xs
countBy xs = countBy' 0 xs
Or more simply
countBy :: (a -> Bool) -> [a] -> Int
countBy cond [] = 0
countBy cond (x:xs)
| cond x = countBy cond xs + 1
| otherwise = countBy cond xs