Generics and Functional programming in Swift

Question

The two variants of the sum function below are my attempt to repeat the lisp version introduced by Abelson and Sussman in the classic "Structure and interpretation of Computer Programs" book in Swift. The first version was used to compute the sum of integers in a range, or the sum of squares of integers in a range, and the second version was used to compute the approximation to pi/8.

I was not able to combine to the versions into a single func which will handle all types. Is there a clever way to use generics or some other Swift language feature to combine the variants?

func sum(term: (Int) -> Int, a: Int, next: (Int) -> Int, b: Int) -> Int {
    if a > b {
        return 0
    }
    return (term(a) + sum(term, next(a), next, b))
}

func sum(term: (Int) -> Float, a: Int, next: (Int) -> Int, b: Int) -> Float {
    if a > b {
        return 0
    }
    return (term(a) + sum(term, next(a), next, b))
}

with

sum({$0}, 1, {$0 + 1}, 3)

6 as result

sum({$0 * $0}, 3, {$0 + 1}, 4)

25 as result

8.0 * sum({1.0 / Float(($0 * ($0 + 2)))}, 1, {$0 + 4}, 2500)

3.14079 as result

Answer 1

To make it a bit easier I have changed the method signatures slightly and assume that it is good enough to work for func sum_ <T> (term: (T -> T), a: T, next: (T -> T), b: T) -> T {, where T is some kind of number.

Unfortunately there is no Number type in Swift, so we need to make our own. Our type needs to support

• addition
• comparison
• 0 (the neutral element for addition)

New Protocols for the requirements of the function

Comparison is handled in the Comparable protocol, for the reset we can create our own protocols:

protocol NeutralAdditionElementProvider {
    class func neutralAdditionElement () -> Self
}

protocol Addable {
    func + (lhs: Self, rhs: Self) -> Self
}

sum implementation

We can now implement the sum function:

func sum <T where T:Addable, T:NeutralAdditionElementProvider, T:Comparable> (term: (T -> T), a: T, next: (T -> T), b: T) -> T {
    if a > b {
        return T.neutralAdditionElement()
    }
    return term(a) + sum(term, next(a), next, b)
}

Making Int and Double conform to the protocols

+ is already implemented for Double and Int so protocol conformance is easy:

extension Double: Addable {}

extension Int: Addable {}

Providing a neutral element:

extension Int: NeutralAdditionElementProvider {
    static func neutralAdditionElement() -> Int {
        return 0
    }
}

extension Double: NeutralAdditionElementProvider {
    static func neutralAdditionElement() -> Double {
        return 0.0
    }
}

Answer 2

Sebastian answers your question (+1), but there might be other simple functional solutions that leverage existing generic functions (such as reduce, which is frequently used for sum-like calculations). Perhaps:

let π = [Int](0 ..< 625)
    .map { Double($0 * 4 + 1) }
    .reduce(0.0) { return $0 + (8.0 / ($1 * ($1 + 2.0))) }

Or:

let π = [Int](0 ..< 625).reduce(0.0) {
    let x = Double($1 * 4 + 1)
    return $0 + (8.0 / (x * (x + 2.0)))
}

These both generate an answer of 3.14079265371779, same as your routine.

---

If you really want to write your own generic function that does this (i.e. you don't want to use an array, such as above), you can simplify the process by getting the + operator out of the sum function. As Sebastian's answer points out, when you try to perform addition on a generic type, you have to jump through all sorts of hoops to define a protocol that specifies that the types that support + operator and then define these numeric types as conforming to that Addable protocol.

While that's technically correct, if you have to define each numeric type that you might use in conjunction with this sum function as being Addable, I'd contend that this is no longer in the spirit of generic programming. I'd suggest you rip a page out of the reduce book, and let the closure that you pass to this function do the addition itself. That eliminates the need to need to define your generics as being Addable. So that might look like (where T is the type for the sum that will be calculated and U is the type for index that is being incremented):

func apply<T, U: Comparable>(initial: T, term: (T, U) -> T, a: U, next: (U) -> U, b: U) -> T {
    let value = term(initial, a)
    if a < b {
        return apply(value, term, next(a), next, b)
    } else {
        return value
    }
}

And you'd call that like so:

let π = apply(Double(0.0), { return $0 + 8.0 / Double((Double($1) * Double($1 + 2))) }, 1, { $0 + 4}, 2500)

Note, it's no longer a sum function as it's really just a "repeat executing this closure from a to b", hence my choice to rename this to apply.

But as you can see, we've moved the addition into the closure we pass to this function. But it gets you out of the silliness of having to redefine every numeric type you want to pass to the "generic" function as being Addable.

Note, this also addresses another problem that Sebastian solved for you, namely the need to implement neutralAdditionElement for every numeric data type, too. That was necessary to perform a literal translation of the code you provided (i.e. to return zero if a > b). But I've changed the loop such that rather than returning zero when a > b, it returns the calculated term value if a == b (or greater).

Now, this new generic function can be used with any numeric types, without needing to implement any special functions or make them conform to any special protocols. Frankly, there's still room for improvement here (I'd probably considering using a Range or SequenceType or something like that), but it gets to the your original question of how to use generic functions to calculate the sum of a series of evaluated expressions. To make it behave in a truly generic manner, the answer is probably "get the + out of the generic function and move it to the closure".