Add `count`

[chuckwondo]

I'd like to suggest adding a count function to count the number of elements that match a predicate.

Perhaps something like so:

count :: forall a f. Foldable f => (a -> Boolean) -> f a -> Int
count p = foldl (\n x -> if p x then n + 1 else n) 0

[JordanMartinez]

I think I'm against adding this. AFAIK, most common Foldable types (e.g. Array, Map, etc.) have a count-like function (e.g. size, length) that is monomorphic and doesn't incur the cost of type class dictionaries. Since this function is relatively simple to define in local usages, I don't think it's worth adding here.

Feel free to disagree with me, but I'll close this for now.

[chuckwondo]

Perhaps because I'm a noob to PS (and to FP in general), I'm going to disagree, so I might just need to be enlightened. I'm all ears if my argument isn't valid.

The difference in what I'm proposing is the use of a predicate, distinguishing the proposed count function from the length function, which makes the count function a counterpart to the filter function.

In essence, count is counting the number of elements in the result of applying filter, but without incurring the cost of generating the result of filter. In other words, count pred xs is equivalent to length $ filter pred xs, but it doesn't create the intermediate result of filter, which is simply thrown away because it is not needed. It is the unnecessary cost of generating the unused intermediate result that I'm trying to avoid with my proposal for count.

Again, I'm all ears if what I'm proposing doesn't make sense, or if there is some other way to achieve this that I'm not aware of, without having to implement my own count everywhere I need it.

As you said, however, this really is simple to define in local usages, so perhaps this is reason enough to avoid adding the proposed count function. Although, I feel like this could be an argument for many function that are included in many libraries, so I'm not sure I fully agree on this point. Such functions may be 1-liners, but they are 1-liners that you don't want to have to remember how to correctly reimplement in local usages, which is why they've been added to libraries.

No worries if you still disagree. I appreciate your time and consideration, and look forward to deepening my PS and FP knowledge.

[garyb]

I think the proposed count does seem like a reasonable addition to this library. It seems more closely related to any / all than length / size.

[JordanMartinez]

Most of my argument comes from the principle of not being quick to add things to core libraries and whether something simple like this passes the Fairbairn Threshold. If something was added, but the API wasn't quite right, then we have to fix it via a breaking change, which doesn't happen very often, so we're stuck with the design for a while. Clearly, this definition isn't liable to such a problem because that's the only way it can be defined.

Since Gary is good with this addition, then I'll remove my stance against this.

[garyb]

Well, now you mention it... I suppose it could be defined with Semiring instead of Int! Or even Monoid if one was taken as an argument, but I'm not sure if there's much value in that. Semiring would mean it could count to a larger value (if Number / big-num type thing), but it would potentially make it annoying to use for type inference reasons.

[JordanMartinez]

Yeah, I don't think anyone would be using anything aside from Int.

[garyb]

We do use HeytingAlgebra and Semiring constrained result values in some of the other functions (any / all / sum / product, etc.) but those cases are a little different as the result type also appears in the arguments, so the inference can be directed by that.

We use Int for length / size so I think it probably is a safe assumption to make. If someone does need to count a larger structure then they'd can still fold it themselves, and/or a monomorphic version would probably be significantly faster for a structure of that size.