Implementing generic mathematical function on Collection Types

Using Swift
1

Hi there,

forgive me if this question or a similar one has already been asked or if it's somewhat of a beginner question. I did some googling but it's a bit hard to find the correct search terms. What I'm trying to achieve is to add some generic mathematical functions like average(), median(), mode(), etc. to Collection types. I made some progress but it seems that I need to have two functions for each of these operations with the exact same implementation: one with a Element: BinaryInteger constraint and one with a Element:BinaryFloatingPoint constraint. For example for the average function, this would look like the following:

    func sum() -> Element
    {
        return self.reduce(0, +)
    }
    
    func average() -> Double where Element: BinaryInteger
    {
        return Double(self.sum()) / Double(self.count)
    }
    
    func average() -> Double where Element: BinaryFloatingPoint
    {
        return Double(self.sum()) / Double(self.count)
    }

Is there a way to reduce the code duplication?

kind regards,

Tim

2

Well, you can write your sum function against AdditiveArithmetic, but you’ll still need two separate versions of average because Double does not have an initializer that takes an AdditiveArithmetic instance.

Conversely, you could make a new protocol to encapsulate the idea of “convertible to Double”.

• • •

However, the reality of calculating an average (or even a sum) is quite a bit more intricate than you may realize.

When you sum a collection of signed integers, the partial sums could spuriously overflow even though the final result does not. For example, [100 as Int8, 100, -100, -100] clearly “should” sum to zero, but the first two elements add to 200, which overflows the Int8 type.

And when you sum a collection of floating-point numbers, significant bits could be lost due to order-of-magnitude differences. For example, [16_777_216 as Float, 1, -16_777_216] clearly “should” sum to one, but a naive calculation results in zero.

I have written more about these issues in this thread, including an implementation for integers that solves the first problem, and an implementation for floats that mitigates the second.

• • •

Furthermore, on the subject of average specifically, there exist so-called “online” algorithms for floating-point types, which don’t require calculating the full sum. A similar algorithm exists for the variance / standard deviation, and both can be done with compensated (Kahan) summation to reduce the accumulation of errors.

A while back I wrote a very simple implementation to calculate basic statistics. This version does not perform error correction, but such a change is not too difficult.

3 Likes
3

You should also be aware of the Numeric protocol, which implements addition, subtraction, and multiplication, although, unfortunately, there is no API for converting any Numeric type to Double.

4

I have indeed been looking at the Numeric protocol but indeed could not find any way to convert a Numeric into a Double. I was also browsing through the Swift Numerics package to see if that offered a solution, but as far as I have seen it doesn't.

5

Thanks for your extensive reply! I indeed didn't think about the possibility of overflows. I will have a look at the links you provided to see if I can use your suggestions to improve my code :smiley: