浅谈Swift中的函数式

对于一个数学专业毕业的学生，函数式编程天然的吸引力了我，从哥德尔的不完备定理，到邱奇的lambda演算，到柯里的组合子逻辑，无不吸引着我。 而swift作为一门多编程范式的语言，同样支持函数式编程。 不过函数式编程比较复杂，我也只是管中窥豹，谈谈自己在swift中的认识。

函数式的数据结构

函数式编程和命令式编程不一样，进行纯函数式编程，由于无法进行赋值操作(不可变的数据结构)，而在C或者是C++这样的语言中数据结构往往都是可变的，所以以前所学的数据结构和算法都没有什么用。 由于数据结构的不同，禁止赋值，有额外的开销，算法也不一样。

Binary Search Tree 插入算法

常见的数据结构

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}
复制代码

和它的插入算法

func insertIntoBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        guard let rootNode = root  else {
            return TreeNode(val)
        }
        if val < rootNode.val {
            rootNode.left = insertIntoBST(rootNode.left, val)
        } else {
            rootNode.right = insertIntoBST(rootNode.right, val)
        }
        return root
    }
复制代码

用函数式的数据结构表示

indirect enum BST {
    case leaf
    case node(BST,Int,BST)
    
    init() {
        self = .leaf
    }
    init(_ value: Int) {
        self = .node(.leaf,value,.leaf)
    }
}
复制代码

同样的，函数式的插入算法

func insertIntoBST(_ root:BST, _ val:Int) -> BST {
        switch root {
        case .leaf:
            return BST(val)
        case let .node(left, value, right):
            if val < value {
                return BST.node(insertIntoBST(left, val), value, right)
            } else {
                return BST.node(left, value, insertIntoBST(right, val))
            }
        }
    }
复制代码

可以看到由于不可变的数据结构，不能对树做修改，要实现插入算法，必须每次都创建新的树。

一等函数

第一次接触swift最大的印象就是函数是一等公民，可以作为参数传递。

比如下面这个 fibF

func fib(_ n:Int) -> Int {
    if n < 2 {
        return n
    } else {
        return fib(n-1) + fib(n-2)
    }
}
let fibF = fib
fibF(11)
复制代码

或者我们不想显式的定义 fib 这个函数，使用Z组合子

func Z<T,U>(f:@escaping ((T) -> U, T) -> U) -> (T) -> U {
    return {(x:T) -> U in f(Z(f: f),x)}
}
let fibZ = Z(f: {$1 < 2 ? $1 : $0($1-1) + $0($1-2)})
fibZ(11)
复制代码

在系统提供的方法中也很常见，比如Array的 sorted 方法就可以传一个函数

[1,2,3,4,5].sorted(by: >)
复制代码

一等函数的概念源自邱奇的lambda演算。 现代计算机采用的是冯诺伊曼结构，而冯诺依曼结构是图灵机的一个实现。然而在图灵为了解决判定性问题引入图灵机，和他同时代的天才，邱奇，在几个月前用lambda演算和递归函数，证明了类似的论题。这三个模型（图灵机，lambda演算和递归函数）计算能力等价(邱奇-图灵猜想)。

算子

高阶函数 map与flatMap

什么函数式编程呢，可能很多人最大的印象就是使用map和flatMap这样的高阶函数，当然这只是一部分

在swift中 Optionals 和 Collection 有map和flatMap函数 map函数

(1...10).map({"\($0)"}) 
复制代码

flatMap函数

["Hi","Swift"].flatMap({$0})
复制代码

Functor与Monad

为什么 Optionals 和 Array 会有同样的名称的方法? 这些map和flatMap方法是否遵守相同的逻辑？

我们可以看下swift中对 Optionals 的map函数的定义

@inlinable public func map<U>(_ transform: (Wrapped) throws -> U) rethrows -> U?
复制代码

对 Array 的map函数定义

@inlinable public func map<T>(_ transform: (Bound) throws -> T) rethrows -> [T]
复制代码

Haskell中 Functor 有个函数 fmap (swift中的map)

fmap :: (a -> b) -> [a] -> [b]
复制代码

所以它们被称为Functor(函子)

相应的查看一下swift中对flatMap的定义

//Optionals
@inlinable public func flatMap<U>(_ transform: (Wrapped) throws -> U?) rethrows -> U?
//Array
@inlinable public func flatMap<SegmentOfResult>(_ transform: (Element) throws -> SegmentOfResult) rethrows -> [SegmentOfResult.Element] where SegmentOfResult : Sequence
复制代码

Haskell中 Monad 对函数 >>= 的定义(swift中的flatMap)

(>>=) :: m a -> (a -> m b) -> m b
复制代码

翻译成swift就是(伪代码)

func flatMap<A,B>(x:F<A>)(_ transform: (A) -> F<B>) -> F<B>
复制代码

可见 Optionals 和 Array 都是Monad