Functional Programming in Swift(三)

Chapter 4 Map, Filter, Reduce

本文是《Functional Programming in Swift》中第四章的笔记,如果你感兴趣,请购买英文原版。

一个函数A使用另一个函数 B 作为参数,我们可以称这个 A 函数是一个高阶函数,本节我们来探寻一下高阶函数在 Swift standard library 中数组上面的一些应用。为了搞懂这些,首先来介绍一下泛型

1. Introducing Generics

我们有一个整型数组,现在需要写一个 function 返回一个数组,使其所有元素都加 1:

func incrementArray(xs: [Int]) -> [Int] {  
    var result: [Int] = [ ]
    for x in xs {
        result.append(x + 1) 
    }
    return result 
}

再写另外一个 function,返回一个数组,使其所有元素都 ×2:

func doubleArray1(xs: [Int]) -> [Int] {  
    var result: [Int] = [ ]
    for x in xs {
        result.append(x * 2) 
    }
    return result
}

这些函数都共享相同的代码,我们能否抽象相同和不同的部分,写出更加通用的 function 呢,比如:

func computeIntArray(xs: [Int]) -> [Int] {  
    var result: [Int] = [ ]
    for x in xs {
        result.append(/* something using x */) 
    }
    return result 
}

为了实现这一目标,我们添加一个函数作为参数,这个函数描述了如何计算数组中的每一个元素:

func computeIntArray(xs: [Int], f: Int -> Int) -> [Int] {  
    var result: [Int] = [ ]
    for x in xs {
        result.append(f(x)) 
    }
    return result 
}

现在我们就能根据需要传入不同的参数(function)来满足我们的需要,这样实现 doubleArray 和 incrementArray 只需要一行代码调用 computeIntArray: 就能实现:

func doubleArray2(xs: [Int]) -> [Int] {  
    return computeIntArray(xs) { x in x * 2 }
}

注意上面的 function 的第二个参数使用了尾随闭包。虽然改造过的函数具备了一定的通用性,但还不够彻底,比如我们想判断这个整型数组所有元素的奇偶性,返回一个包含 BOOL 类型的结果数组,我们可以这么写:

func isEvenArray(xs: [Int]) -> [Bool] {  
    computeIntArray(xs) { x in x % 2 == 0 }
}

不幸的是上面的函数会报错,因为 computeIntArray 函数接收的第二个参数是 Int -> Int 类型,而我们传进来的却是 Int -> Bool。解决的办法之一是定义一个新的 computeBoolArray 函数:

func computeBoolArray(xs: [Int], f: Int -> Bool) -> [Bool] {  
    let result: [Bool] = [ ]
    for x in xs {
        result.append(f(x)) 
    }
    return result 
}

虽然问题解决了,但并不是具有“弹性”,下一次如果要计算 String 类型呢,难道还要定义一个 Int -> String 函数么。

幸运的是,我们可以使用泛型( generics )。computeBoolArray 和 computeIntArray 仅仅是参数不同而已,我们下面写一个通用版本:

func genericComputeArray<U>(xs: [Int], f: Int -> U) -> [U] {  
    var result: [U] = [ ]
    for x in xs {
        result.append(f(x)) 
    }
    return result 
}

这里的 “U” 是类型签名,所有的函数中所有的 U 都是相同类型,我们继续深入一步:把整型数组变的更为通用的一般数组:

func map<T, U>(xs: [T], f: T -> U) -> [U] {  
    var result: [U] = [ ]
    for x in xs {
        result.append(f(x)) 
    }
    return result 
}

这里我们写了一个 map 函数,他带两个参数:元素类型为 T 的数组,和类型为 T -> U 的 function ,这个 map 函数最终返回一个元素类型为 U 的数组。这个map函数比之前的 genericComputeArray 更为通用,我们可以这样定义 genericComputeArray:

func computeIntArray<T>(xs: [Int], f: Int -> T) -> [T] {  
    return map(xs, f)
}

实际上,swift 的标准库已经定义了 map 方法,我们可以直接通过 xs.map(f) 来调用,比如:

func doubleArray3(xs: [Int]) -> [Int] {  
    return xs.map { x in 2 * x }
}

2. Filter

map 方法不是 swift 基本库中唯一用到泛型的函数,下面介绍其他一些方法。假设有一个数组如下:

let exampleFiles = ["README.md", "HelloWorld.swift", "HelloSwift.swift", "FlappyBird.swift"]  

但我们想要一个只包含 swift 文件的数组:

func getSwiftFiles(files: [String]) -> [String] {  
    var result: [String] = [ ]
    for file in files {
        if file.hasSuffix(".swift") { 
            result.append(file)
        }
    }
    return result 
}

// 调用
getSwiftFiles(exampleFiles)

> [HelloWorld.swift, HelloSwift.swift, FlappyBird.swift]

我们用更通用的方式来改写,首先定义一个 check 类型:T -> Bool,来 check 数组中的每一个元素,并输出:

func filter<T>(xs: [T], check: T -> Bool) -> [T] {  
    var result: [T] = [ ]
    for x in xs {
        if check(x) { 
            result.append(x)
        } 
    }
    return result 
}

定义一个过滤 swift 文件的方法:

func getSwiftFiles2(files: [String]) -> [String] {  
    return filter(files) { 
        file in file.hasSuffix(".swift") 
    }
}

其实和 map 方法一样,swift 基本库也提供了原生的 filter 方法,我们可以直接调用:

exampleFiles.filter { file in file.hasSuffix(".swift") } 

> [HelloWorld.swift, HelloSwift.swift, FlappyBird.swift]

3. Reduce

本节我们先来看几个简单的函数,首先是对一个整型数组的所有元素求和:

func sum(xs: [Int]) -> Int {  
    var result: Int = 0
    for x in xs {
        result += x 
    }
    return result 
}

let xs = [1, 2, 3, 4] sum(xs)  
> 10

对整型数组所有元素求乘积:

func product(xs: [Int]) -> Int {  
    var result: Int = 1
    for x in xs {
        result = x * result 
    }
    return result 
}

组合一个字符串:

func concatenate(xs: [String]) -> String {  
    var result: String = ""
    for x in xs {
        result += x 
    }
    return result 
}

我们还可以提供一个header line:

func prettyPrintArray(xs: [String]) -> String {  
    var result: String = "Entries in the array xs:\n" 
    for x in xs {
        result=" "+result+x+"\n" 
    }
    return result 
}

以上这些方法有两个部分可抽象,result的初始值,在循环中用来更新result的 function,我们按照这个思想来定义一个 reduce function:

// 一个任意类型的输入数组 [A],将要计算出结果类型 R,一个用来更新结果的 function :(R,A) -> R
func reduce<A, R>(arr: [A],  
                    initialValue: R,
                    combine: (R, A) -> R) -> R {
    var result = initialValue 
    for i in arr {
        result = combine(result, i) 
    }
    return result 
}

我们现在可以用 reduce fucntion 来重新实现之前那些 simple function:

// 求和
func sumUsingReduce(xs: [Int]) -> Int {  
    return reduce(xs, 0) { result, x in result + x }
}
// 乘积
func productUsingReduce(xs: [Int]) -> Int {  
    return reduce(xs, 1, *)
}
// 字符串拼接
func concatUsingReduce(xs: [String]) -> String {  
    return reduce(xs, "", +)
}

reduce 也是 swift 基本库原生实现的,我们可以直接通过 xs.reduce(initialValue, combine) 来使用。我们也可以使用 reduce 来构造新的泛型函数,比如有一个包含数组的数组,我们将所有元素导出到一个数组中。首先我们用普通的方法来写:

func flatten<T>(xss: [[T]]) -> [T] {  
    var result : [T] = [ ]
    for xs in xss {
        result += xs 
    }
    return result 
}

改用 reduce :

func flattenUsingReduce<T>(xss: [[T]]) -> [T] {  
    return xss.reduce([ ]) { result, xs in result + xs }
}

事实上,我们还可以用 reduce 来重新定义 map 和 filter:

// map
func mapUsingReduce<T, U>(xs: [T], f: T -> U) -> [U] {  
    return xs.reduce([ ]) { result, x in result + [f(x)] }
}
// filter
func filterUsingReduce<T>(xs: [T], check: T -> Bool) -> [T] {  
    return xs.reduce([ ]) { result, x in
        return check(x) ? result + [x] : result 
    }
}

以上例子展示了 reduce 的本质:就是遍历数组中的元素来计算最终结果。

4. Putting It All Together

现在我们来看一个实际的例子,假定我们有一个 struct City 定义如下:

struct City {  
    let name: String 
    let population: Int
}

然后我们定义一些城市,并将他们放到一个数组中:

// 人口(单位:千)
let paris = City(name: "Paris", population: 2243)  
let madrid = City(name: "Madrid", population: 3216)  
let amsterdam = City(name: "Amsterdam", population: 811)  
let berlin = City(name: "Berlin", population: 3397)

let cities = [paris, madrid, amsterdam, berlin]  

假定我们需要打印常住人口至少一百万的城市,我们先定义一个 scale 函数来转换人口单位:

func scale(city: City) -> City {  
    return City(name: city.name, population: city.population * 1000)
}

接着,我们就用本章所接触的函数来实现这个方法

cities.filter({ city in city.population > 1000 })  
       .map(scale)
       .reduce("City: Population") { result, c in
            return result + "\n" + "\(c.name) : \(c.population)"
        }

> City: Population 
> Paris : 2243000 
> Madrid : 3216000 
> Berlin : 3397000

首先,我们用 filter 筛选出人口不小于一百万的城市,然后用 map 遍历所有城市转换人口单位,最后用 reduce 将字符串拼接起来。

5. Generics vs. the Any Type

除了泛型,swift 还提供了 Any type 来表示任意类型,表面上和泛型类似,他们都可以用在函数上表示接受不同的类型的参数,但是他们很重要的区别就是:泛型通常用来定义 flexible fucntion,编译器仍然可以检查类型。但是 Any type 躲开了 swift 的类型检查。

// 返回类型是T,编译器可以判断
func noOp<T>(x: T) -> T {  
    return x
}
// 返回类型不确定,编译器不知道,可能呢引起运行时错误
func noOpAny(x: Any) -> Any {  
    return x
}

最后,泛型中的类型可以提供很多信息,比如我们可以定义 >>> 的泛型版本:

infix operator >>> { associativity left }  
func >>> <A, B, C>(f: A -> B, g: B -> C) -> A -> C {  
    return { x in g(f(x)) } 
}

同样的方式,我们可以泛型一个柯理化:

func curry<A, B, C>(f: (A, B) -> C) -> A -> B -> C {  
    return { x in { y in f(x, y) } }
}

这样我们就定义了一个转换函数,将一个非柯理化的函数转换成柯理化的函数。

使用泛型,我们可以写出灵活性和扩展性都很强的函数而不必受制于类型安全。

6. Notes

泛型的历史可以追溯到很久之前( Strachey (2000), Girard’s System F (1972), and Reynolds (1974))不过这些作者提到的泛型指多态,现在很多面向对象语言都在使用多态做来自与子类的隐式转换,而这里的泛型消除了二者的歧义。


-EOF-

如果感觉此文对你有帮助,请随意打赏支持作者 😘

chengway

认清生活真相之后依然热爱它!

Subscribe to Talk is cheap, Show me the world!

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!