Haskell using Higher-Order Functions to count how many items there are in a list

Question

I'm trying to write a line of Haskell that count the number of items in a list that are between two stated upper and lower bounds, e.g. countBetween 3 6 [5, 9, 2, 4, 6, 3, 1, 4] = 5 since 5, 4, 6, 3 & 4 are between the bounds 3 and 6.

So far I have:

countBetween x1 x2 = filter (>=x1) . filter (<=x2)

Which filters the list to only include numbers that are within those bounds, but I don't know how to count how many items that list possesses. My initial thoughts is that it would use foldr?

Answer 1

To turn my comment into an answer:

You need to use the length function. In this case you would compose it with what you already have as

countBetween lower upper = length . filter (>= lower) . filter (<= upper)

Alternatively, you could define your function with its full arguments as

countBetween lower upper xs = length $ filter (>= lower) $ filter (<= upper) xs

The general rule of thumb for eta reduction is to first turn all your $s into .s and add a $ before the last argument, so the above line becomes

countBetween lower upper xs = length . filter (>= lower) . filter (<= upper) $ xs

Then you look to see if the last argument to your definition is also the last argument to your expression, and it's the only place in your expression that the argument appears

countBetween lower upper xs = length . filter (>= lower) . filter (<= upper) $ xs
--                       ^                                                     ^

These can now be removed, leaving you with

countBetween lower upper = length . filter (>= lower) . filter (<= upper)

Then repeat. In this case, you can't eta reduce any more (easily), so you're done!

I would also recommend defining your functions with full arguments to begin with then slowly introducing point free versions. Sometimes it's fun to find clever ways to eta reduce expressions, but while it's possible to push it further with some definitions, it isn't always recommended. Only do it where it's natural and makes it easier to read. For example, using the pointfree tool from the pointfree package, you can eta reduce your definition all the way to

 countBetween = ((length .) .) . (. (filter . flip (<=))) . (.) . filter . flip (>=)

But this is hardly readable. Don't do this.

Answer 2

To answer this directly, there's a Haskell tool called hoogle. We'd expect the type of a length function to be [a] -> Int and if we search this verbatim in hoogle we end up with

 length :: [a] -> Int

So

countBetween x y = length . filter (>= x) . filter (<= y)

Note the dot since we're continuing to compose functions.

Answer 3

While using the built-in length function is certainly preferrable, here's a solution using a "poor man's length" with foldr:

countBetween x1 x2 = foldr (\v len -> len + 1) (0) . filter (>= x1) . filter (<= x2)

The length is computed by foldr:

• we start with an accumulator of 0
• for every list element v, we simply add 1 to our accumulator