Swift 中的泛型和函数式编程

Question

下面求和函数的两个变体是我尝试重复 Abelson 和 Sussman 在 Swift 的经典 "Structure and interpretation of Computer Programs" 书中介绍的 lisp 版本。第一个版本用于计算范围内整数的总和，或范围内整数的平方和，第二个版本用于计算 pi/8 的近似值。

我无法将这些版本组合成一个可以处理所有类型的函数。有没有聪明的方法来使用泛型或其他一些 Swift 语言特性来组合变体？

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))
}

与

sum({[=12=]}, 1, {[=12=] + 1}, 3)

结果为 6

sum({[=13=] * [=13=]}, 3, {[=13=] + 1}, 4)

结果为 25

8.0 * sum({1.0 / Float(([=14=] * ([=14=] + 2)))}, 1, {[=14=] + 4}, 2500)

结果为 3.14079

Answer 1

为了让它更容易一些，我稍微更改了方法签名并假设它足以用于 func sum_ <T> (term: (T -> T), a: T, next: (T -> T), b: T) -> T {，其中 T 是某种数字。

遗憾的是Swift中没有Number类型，所以我们需要自己制作。我们的类型需要支持

加法
比较
0（加法的中性元素）

满足功能要求的新协议

比较在 Comparable 协议中处理，对于重置我们可以创建自己的协议：

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

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

`sum`实施

我们现在可以实现 sum 功能：

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)
}

使 `Int` 和 `Double` 符合协议

+ 已经为 Double 和 Int 实现，因此协议一致性很容易：

extension Double: Addable {}

extension Int: Addable {}

提供中性元素：

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

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

Answer 2

Sebastian 回答了您的问题 (+1)，但可能还有其他利用现有泛型函数的简单函数解决方案（例如 reduce，经常用于类似 sum 的计算） .也许：

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

或：

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

这些都会生成 3.14079265371779 的答案，与您的例程相同。

如果你真的想编写自己的通用函数来执行此操作（即你不想使用数组，如上），你可以通过获取 + 运算符来简化过程sum 函数。正如塞巴斯蒂安的回答所指出的那样，当您尝试对泛型类型执行加法时，您必须跳过各种步骤来定义一个协议，该协议指定支持 + 运算符的类型，然后将这些数字类型定义为符合 Addable 协议。

虽然这在技术上是正确的，但如果您必须将可能与此 sum 函数结合使用的每个数字类型定义为 Addable，我认为这不再适用泛型编程的精神。我建议您从 reduce 书中撕下一页，让您传递给此函数的闭包自行执行加法。这消除了将泛型定义为 Addable 的需要。所以这可能看起来像（其中 T 是将要计算的总和的类型，U 是要递增的索引的类型）：

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
    }
}

你可以这样称呼它：

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

请注意，它不再是 sum 函数，因为它实际上只是一个 "repeat executing this closure from a to b"，因此我选择将其重命名为 apply。

但如您所见，我们已将加法移至传递给该函数的闭包中。但这让您摆脱了必须将要传递给 "generic" 函数的每个数字类型重新定义为 Addable.

的愚蠢行为

注意，这也解决了 Sebastian 为您解决的另一个问题，即也需要为每种数字数据类型实现 neutralAdditionElement。这是执行您提供的代码的字面翻译所必需的（即如果 a > b 则 return 为零）。但是我已经改变了循环，而不是 return 在 a > b 时为零，如果 a == b （或更大），它 return 是计算的 term 值.

现在，这个新的泛型函数可以用于任何数字类型，无需实现任何特殊函数或使其符合任何特殊协议。坦率地说，这里仍有改进的余地（我可能会考虑使用 Range 或 SequenceType 或类似的东西），但它涉及到您最初的问题，即如何使用泛型函数来计算一系列评估表达式的总和。要使其以真正通用的方式运行，答案可能是 "get the + out of the generic function and move it to the closure"。

Answer 3

has a decent way to make this "work" for a simple test case. However, as 注意，像 Addable 协议这样的东西并不完全符合函数式编程的精神（或者 Swift 一般而言，也许）。这些解决方案都是可行的，所以这个答案将更多地涉及 "spirit" 问题。

让我们来讲述四个运算符的故事：

func +(lhs: Int, rhs: Int) -> Int
func +(lhs: Int32, rhs: Int32) -> Int32
func +(lhs: Float, rhs: Float) -> Float
func +(lhs: String, rhs: String) -> String // See note below

其中哪些具有相同的行为？ "Well, obviously the first three are the same," 你可能会说，"and the last one is different: 1 + 1 = 2 regardless of whether you're dealing with Int or Int32, and that of course means the same thing as 1.0 + 1.0 = 2.0. But "1" + "1" = "11", so adding strings is completely different."

这些假设是不正确的——所有四个运算符都有不同的行为。

添加 1 和 2_147_483_647 会发生什么？（让我们暂时忽略 String 的情况——我想我们都同意字符串连接不同于数字加法。Right, JavaScript?）这取决于这些值的类型，也可能取决于其他因素.

如果两者都是 Int... 那么，您是针对 32 位还是 64 位编译的 CPU？ Int 在 32 位上是 Int32 的别名，在 64 位上是 Int64 的别名。刚刚得到一个闪亮的新 iPhone 6？太好了，你的答案是 2_147_483_648.
如果两者都是 Int32（或者如果您是为 32 位编译的）...那么，2_147_483_647 是可能的最大有符号 32 位整数，因此将其加一产生溢出。在 Swift 中，添加 + 运算符会在溢出时陷入陷阱，因此您会崩溃。 Swift 迫使您考虑是否需要溢出行为（通过选择 + 或 &+ 运算符），这样您就不会 blow up your rocket.
如果两者都是 Float，您将得到 2.14748365E+9。但是等等，什么是 Float(2_147_483_648)？那也是 2.14748365E+9 — 添加一个什么也没做！ IEEE 32 位浮点数格式有 24 位尾数，因此如果您添加两个相差超过 2^24 的数字，则没有足够的精度来存储结果——最低有效数字消失。这只是浮点运算可能遇到的所有 wild and wooly 问题的开始。

那么这一切的结果是什么？当加法真的是加法时，我们为什么要争论不休？

Swift 中的每个运算符都是一个单独的函数，因为每个运算符都有不同的行为——更确切地说，每个运算符都定义了一个关于其行为的特定 contract。您知道当您添加两个 Int32 值时，总和必须可以表示为 Int32 否则您将 trap，并且如果您需要处理溢出，您必须以不同的方式做事个案。您知道，当您使用 Floats 时，所有算术都会受到精度问题的影响。定义这些类型的契约决定了这些事情。

Swift 具体来说，以及一般的强类型函数式（-ish）编程语言，往往有严格的类型概念和与之相关的契约，以及关于何时使用的严格规则使用特定类型。这里的想法是 type safety — 始终了解您正在处理的类型有助于您（和编译器）推断这些类型定义的契约。

当您将 + 运算符统一到 Addable 协议之后时，您就隐藏了这些类型之间的差异。当然，您可以使用它来制作一些适用于各种类型的短函数。但是以用模糊类型替换严格定义的类型为代价...而且您使用模糊类型的次数越多，您就越不确定代码在所有情况下将如何处理它们。

^{注意：这个运算符实际上并不在 Swift 库中 — 为了简洁起见，我在这里对其进行了简化。 Strings 的加法实际上是由一个泛型运算符执行的，该运算符适用于所有实现 ExtensibleCollectionType 协议的类型，其中 String 是一个。}

Swift 中的泛型和函数式编程

Generics and Functional programming in Swift

generics

functional-programming

swift

满足功能要求的新协议

`sum`实施

使 `Int` 和 `Double` 符合协议

Swift 中的泛型和函数式编程

Generics and Functional programming in Swift

generics

functional-programming

swift

满足功能要求的新协议

sum实施

使 Int 和 Double 符合协议

`sum`实施

使 `Int` 和 `Double` 符合协议