Haskell - arbitrary condition count

Question

I have a midterm exam about Haskell coming up and I'm trying to write a function that counts elements in a list based on whether each element matches a user-supplied boolean condition.

If the condition is hard coded, it's simple:

countEven :: [Int] -> Int
countEven [] = 0
countEven (h:t) = fromEnum (mod h 2==0)+countEven t

countOdds :: [Int] -> Int
countOdds [] = 0
countOdds (h:t) = fromEnum(mod h 2/=0)+countOdds t

Simple, right? Add the cast of the boolean expression applied to the head to the running total, and you'll have a count of how many elements in the list satisfy that condition.

However, suppose I want to write a higher-order function where I supply the boolean expression and every element in the list is tested against that expression.

This is what I have so far:

countCond :: (Int -> Bool) -> [Int] -> Int
countCond _ [] = 0

Now I'm unsure how I would write the recursive call.

Answer 1

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

Answer 2

Try to decompose the problem into smaller pieces. For instance, you could start by filtering the list according to the user-supplied test function and then return its length. Makes sense?

Answer 3

Well, the recursive call is exactly the same, you just need to replace the condition with a call to the user-supplied function:

countCond f (h:t) = fromEnum(f h) + countCond f t

Answer 4

since the function is going to give you the correct values, just filter:

countCond :: (Int -> Bool) -> [Int] -> Int
countCond f xs = length $ filter f xs

Thus, your previous function would look like:

countOdd xs = length $ filter odd xs

I think that is easier ...