函数式思想

  • 函数是一等值(first-class-value)
  • 核心理念: 函数是值(与struct, int or bool无区别),应使用与变量同一套命名规则。

Currying

将接受多个参数的函数,转变成每次之接受一个参数的调用序列。

func add1(_ x: Int, _ y : Int) -> Int {
    return x + y
}

add1(2,3)
func add2(_ x : Int) -> ((Int) -> Int) {
    return {
        y in return x + y
    }
}

add2(2)(3)

返回闭包

Map, Filter, Reduce

泛型

func swipeInts(a : inout Int, b : inout Int) {
    
}

func swipeStrings(a : inout String, b : inout String) {

}
func swipeValues<T>(a : inout T, b : inout T) {
    
}

The brackets tell Swift that T is a placeholder type name within the swapTwoValues(::) function definition

Naming Type Parameters

Dictionary<Key, Value>

Element in Array<Element>

However, when there isn’t a meaningful relationship between them, it’s traditional to name them using single letters such as T, U, and V, such as T in the swapTwoValues(_:_:) function above.

https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Generics.html

Filter

func filter(includeElement: (T) -> Bool) -> Array<T>

一个例子

var numbers = Array(1...8)

var evenNumbers = numbers.filter { (x) -> Bool in
    x % 2 == 0
}

var oddNumbers = numbers.filter { (x) -> Bool in
    x % 2 != 0
}

返回什么

numbers         //return: [1, 2, 3, 4, 5, 6, 7, 8]
evenNumbers     //return: [2, 4, 6, 8]
oddNumbers      //return: [1, 3, 5, 7]

实现你自己的Filter

func myFilter(includeElement: (Element) -> Bool) -> [Element] {
    var result: [Element] = []
    for x in self where includeElement(x){
        result.append(x)
    }
    return result
}
let arr = [1,2,3,4]
let arr2 = arr.myFilter(includeElement: { $0 > 1 }
print(arr2)	//[2,3,4]

Map

定义

func map<T>(@noescape transform: (Self.Generator.Element) throws -> T) rethrows -> [T]

一个例子

let arr = [1,2,3,4]
let arr3 = arr.map({ $0 + 1 })
print(arr3)	//[2,3,4,5]

实现自己的Map

func myMap<T> (transform: (Element) -> T)-> [T] {
    var result: [T] = []
    for x in self {
        result.append(transform(x))
    }
    return result
}
let arr = [1,2,3,4]
let arr3 = arr.myMap(transform: { $0 + 1 })
print(arr3)	//[2,3,4,5]

扩展: FlatMap

一个例子

let array = [[1,2,3],[4,5,6]]
let array_map = array.map({ $0.map{ $0 + 1 } })
let array_flatMap = array.flatMap({ $0.map{ $0 + 1 } })

print(array_map)		//[[2, 3, 4], [5, 6, 7]]
print(array_flatMap)	//[2, 3, 4, 5, 6, 7]

为什么?

定义

func flatMap<T>(transform: (Self.Generator.Element) throws -> T?) -> [T]
func flatMap<S : SequenceType>(transform: (Self.Generator.Element) -> S) -> [S.Generator.Element]

源码

public func flatMap<S : Sequence>(
    @noescape transform: (${GElement}) throws -> S) rethrows -> [S.${GElement}] {
    var result: [S.${GElement}] = []
    for element in self {
      result.append(contentsOf: try transform(element))
    }
    return result
  }

发生了什么

[1,2,3].map{ $0 + 1 }.append([4,5,6].map{ $0 + 1 })

关于另一个重载 http://swiftcafe.io/2016/03/28/about-map/

Reduce

定义

func reduce<U>(initial: U, combine: @noescape (U, T) -> U) -> U

一个例子

let arr = [1,2,3,4]
let sum = arr.reduce(0) { (result, x) in
    result + x
}

实现自己的Reduce

func myReduce<T>(initial : T, combine: (T, Element) -> T) -> T {
    var result = initial
    for x in self {
        result = combine(result, x)
    }
    return result
}
let sum = arr.myReduce(initial: 0, combine: {result, x in result + x})
let sum2 = arr.myReduce(initial: 1, combine: *)

print("arr sum is \(sum)")		//10
print("arr sum2 is \(sum2)")	//24

参考资料:

The Swift Programming Language : Closure

Swift高階函式

谈谈 Swift 中的 map 和 flatMap

Swift数组中Map,FlatMap,Filter,Reduce的使用

Data Struct

纯函数式数据结构

不可变 >更高层次的抽象。程序员可以以更接近数学的方式思考问题。

更容易理解的代码。由于不存在副作用,无论多少次执行,相同的输入就意味着相同的输出。

更容易测试的代码。

线程安全的代码。

纯函数 >不变性导致另外一个结果,就是纯函数。纯函数即没有副作用的函数,无论多少次执行,相同的输入就意味着相同的输出。一个纯函数的行为并不取决于全局变量、数据库的内容或者网络连接状态。纯代码天然就是模块化的:每个函数都是自包容的,并且都带有定义良好的接口。纯函数具有非常好的特性。它意味着理解起来更简单,更容易组合,测试起来更方便,线程安全性。

参考资料: Swift函数式编程-不变性

链表

C++实现

typedef struct Node{ 
    int data; 
    struct Node *next; 
}

Swift函数式实现

indirect enum List<Element> {
    case Empty 
    case Node(Element,List<Element>)
}
extension List {
    init() {
        self = .Empty
    }

测试一下

let list0 = List<Int>() //Empty

插入

extension List {
func append(_ element : Element) -> List<Element> {
        guard case let .Node(head, tail) = self else {
            return .Node(element, .Empty)
        }
        return .Node(head, tail.append(element))
    }
}

测试一下

let list1 = list0.append(10)	//10

head与tail

extension List {
    var head : Element? {
        guard case let .Node(head, _) = self else {
            return nil
        }
        return head
    }
    var next : List<Element> {
        guard case let .Node(_ , tail) = self else {
            return .Empty
        }
        return tail
    }

测试一下

let list2 = [5,4,6,3,7,2].reduce(list0) {$0.append($1)}
//5->4->6->3->7->2

list2.head	//5
list2.next	//4->6->3->7->2

删除一个元素

extension List where Element:Equatable {
    func remove(_ elem : Element) -> List<Element> {
        switch self {
        case .Empty :
            return .Empty
        case .Node(elem, let tail):
            return tail
        case let .Node(head, tail):
            return .Node(head, tail.remove(elem))
        }
    }
}

继续测试

print(list2.remove(6))
//5->4->3->7->2

其他操作

extension List {
    var count : Int {
        switch self {
        case .Empty:
            return 0
        case .Node(_ , let tail):
            return tail.count + 1
        }
    }
    func isEmpty() -> Bool {
        switch self {
        case .Empty:
            return true
        default:
            return false
        }
    }
}

二分查找树

C++实现

struct BSTNode  
{  
    int val;  
    BSTNode *left;  
    BSTNode *right;  
};  

Swift函数式实现

indirect enum BinarySearchTree<Element: Comparable> {
    case leaf
    case node(BinarySearchTree<Element>, Element, BinarySearchTree<Element>)
}

面向对象(OOP)与函数式(FP)

面向对象:

  • 数据和对数据的操作紧紧耦合
  • 对象隐藏它们操作的实现细节,其他对象调用这些操作只需要通过接口。
  • 核心抽象模型是数据自己
  • 核心活动是组合新对象和拓展已经存在的对象,这是通过加入新的方法实现的。

函数编程:

  • 数据与函数是松耦合的
  • 函数隐藏了它们的实现,语言的抽象是函数,以及将函数组合起来表达。
  • 核心抽象模型是函数,不是数据结构
  • 核心活动是编写新的函数。
  • 变量缺省是不变的,减少可变性变量的使用,并发性好

推荐阅读:

编程的宗派

纯函数式编程的缺点