Swift函数式编程001

最近在读<Functional Thinking>, 书中描述了各种语言的实现, 唯独不见Swift, 不开心. 补上~

关于完美数, 可以参考维基百科上的描述:完美数(貌似竟然需要梯子, 我chao到底怎么啦?).

完美数分类

public func factorsOf(number: Int) -> [Int] {
    print("2 calculating")
    return Range(1...number).filter { potential in
        return number % potential == 0
    }
}
public func aliquotSum(number: Int) -> Int{
    return factorsOf(number).reduce(0, combine: +) - number
}
public func isPerfect(number: Int) -> Bool {
    return aliquotSum(number) == number
}
public func isAbundant(number: Int) -> Bool {
    return aliquotSum(number) > number
}
public func isDeficient(number: Int) -> Bool {
    return aliquotSum(number) < number
}
for number in 28...30 {
    if isPerfect(number) { print("Perfect") }
    else if isAbundant(number) { print("Abundant") }
    else if isDeficient(number) { print("Deficient") }
}

书上同时说明了这个实现有一个性能问题, 那就是factorsOf会被反复调用多次:

2 calculating
Perfect
2 calculating
2 calculating
2 calculating
Deficient
2 calculating
2 calculating
Abundant

为此, 我们需要一个对函数结果的缓存

func memoize<T:Hashable, U>(fn : T -> U) -> T -> U {
    var cache = [T:U]()
    return {
        (val : T) -> U in
        if cache.indexForKey(val) == nil {
            cache[val] = fn(val)
        }
        return cache[val]!
    }
}
var factorsOf: (Int) -> [Int] = memoize { number in
    print("1 calculating")
    return Range(1...number).filter { potential in
        return number % potential == 0
    }
}

这时候的输出将是:

1 calculating
Perfect
1 calculating
Deficient
1 calculating
Abundant

其中memoize这个函数可以稍微解析一下:

1. 它是一个泛型函数, 它接受一个唯一的参数, 参数名是fn, fn的类型是一个函数类型. 此函数类型是有一个参数(类型T)返回一个结果(类型U). 这个泛型函数的返回类型也是函数类型, 该函数类型也是有一个参数(类型T)返回一个结果(类型U), 也就是跟fn的类型一样. 函数的参数fn就是我们要缓存结果的函数了. 这里我们只支持有一个参数和一个返回结果的函数. 并且使用参数作为key, 函数返回结果作为Value缓存到一个字典里头.
2. 函数首先定义一个cache的字典类型变量, 这个字典的Key类型就是我们缓存函数的参数类型, Value类型是我们缓存函数的返回值类型.
3. 接着函数就返回一个闭包, 这个闭包的参数和返回值类型和我们要缓存的参数的签名是一致的.

这个memoize 必须依赖一个事实, 它缓存的函数必须是没有副作用的, 也就是相同的输入必然会得到相同的输出. 这也是函数式编程的基本要求.
完整实现如下:

func memoize<T:Hashable, U>(fn : T -> U) -> T -> U {
    var cache = [T:U]()
    return {
        (val : T) -> U in
        if cache.indexForKey(val) == nil {
            cache[val] = fn(val)
        }
        return cache[val]!
    }
}
var factorsOf: (Int) -> [Int] = memoize { number in
    print("1 calculating")
    return Range(1...number).filter { potential in
        return number % potential == 0
    }
}
public func factorsOf(number: Int) -> [Int] {
    print("2 calculating")
    return Range(1...number).filter { potential in
        return number % potential == 0
    }
}
public func aliquotSum(number: Int) -> Int{
    return factorsOf(number).reduce(0, combine: +) - number
}
public func isPerfect(number: Int) -> Bool {
    return aliquotSum(number) == number
}
public func isAbundant(number: Int) -> Bool {
    return aliquotSum(number) > number
}
public func isDeficient(number: Int) -> Bool {
    return aliquotSum(number) < number
}
for number in 28...30 {
    if isPerfect(number) { print("Perfect") }
    else if isAbundant(number) { print("Abundant") }
    else if isDeficient(number) { print("Deficient") }
}

没错, 你没有眼花, 我们用一个一样名字的变量factorsOf, 它是一个闭包类型. 后面的代码一点没变, 这个完整实现, 编译是不会报错的,运行也正如我们期望的. 那么, Swift咋的就知道是调用我们的闭包而不是原来的factorsOf函数呢? 这个问题问得好, 我也觉得好神奇! 知道的水友请不吝赐教!

Swift恐怖的地方在于, 添加一些新的代码, 居然可以影响到原先运行得好好的代码, 巨恐怖的感觉.
这Swift 又是泛型, 又是函数式编程, 又是面向协议的. 各种"高大上". 真不敢相信为啥Swift会被打上简单易学的标签的...