对于一个数学专业毕业的学生，函数式编程天然的吸引力了我，从哥德尔的不完备定理，到邱奇的lambda演算，到柯里的组合子逻辑，无不吸引着我。 而swift作为一门多编程范式的语言，同样支持函数式编程。 不过函数式编程比较复杂，我也只是管中窥豹，谈谈自己在swift中的认识。
函数式的数据结构
函数式编程和命令式编程不一样，进行纯函数式编程，由于无法进行赋值操作(不可变的数据结构)，而在C或者是C++这样的语言中数据结构往往都是可变的，所以以前所学的数据结构和算法都没有什么用。 由于数据结构的不同，禁止赋值，有额外的开销，算法也不一样。
Binary Search Tree 插入算法
常见的数据结构
publicclassTreeNode{publicvarval:Intpublicvarleft:TreeNode?publicvarright:TreeNode?publicinit(_val:Int) {self.val = valself.left=nilself.right=nil}}复制代码
和它的插入算法
funcinsertIntoBST(_root: TreeNode?,_val: Int)->TreeNode? {guardletrootNode = rootelse{returnTreeNode(val) }ifval < rootNode.val { rootNode.left= insertIntoBST(rootNode.left, val) }else{ rootNode.right= insertIntoBST(rootNode.right, val) }returnroot }复制代码
用函数式的数据结构表示
indirectenumBST{caseleafcasenode(BST,Int,BST)init() {self= .leaf }init(_value:Int) {self= .node(.leaf,value,.leaf) }}复制代码
同样的，函数式的插入算法
funcinsertIntoBST(_root:BST,_val:Int)->BST{switchroot {case.leaf:returnBST(val)caselet.node(left, value,right):ifval < value {returnBST.node(insertIntoBST(left, val), value,right) }else{returnBST.node(left, value, insertIntoBST(right, val)) } } }复制代码
可以看到由于不可变的数据结构，不能对树做修改，要实现插入算法，必须每次都创建新的树。
一等函数
第一次接触swift最大的印象就是函数是一等公民，可以作为参数传递。
比如下面这个fibF
funcfib(_n:Int)->Int{ifn <2{returnn }else{returnfib(n-1) + fib(n-2) }}letfibF = fibfibF(11)复制代码
或者我们不想显式的定义fib这个函数，使用Z组合子
funcZ(f:@escaping((T)->U,T) ->U) -> (T) ->U{return{(x:T) ->Uinf(Z(f: f),x)}}letfibZ =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函数的定义
@inlinablepublicfuncmap(_transform:(Wrapped)throws->U)rethrows->U?复制代码
对Array的map函数定义
@inlinablepublicfuncmap(_transform:(Bound)throws->T)rethrows-> [T]复制代码
Haskell中Functor有个函数fmap(swift中的map)
fmap:: (a -> b) -> [a] -> [b]复制代码
所以它们被称为Functor(函子)
相应的查看一下swift中对flatMap的定义
//Optionals@inlinablepublicfuncflatMap(_transform:(Wrapped)throws->U?)rethrows->U?//Array@inlinablepublicfuncflatMap(_transform:(Element)throws->SegmentOfResult)rethrows-> [SegmentOfResult.Element]whereSegmentOfResult:Sequence复制代码
Haskell中Monad对函数>>=的定义(swift中的flatMap)
(>>=) :: m a -> (a -> m b) -> m b复制代码
翻译成swift就是(伪代码)
funcflatMap(x:F<A>)(_transform: (A) ->F) ->F复制代码
可见Optionals和Array都是Monad
面向对象与函数式
swift虽然支持函数式编程，然而在实际开发的时候，纯函数编程并非好的选择，因为传统的算法和数据结构都是以图灵机和过程式语言为基础，而且由于数据的不可变性放弃了执行机可以反复擦写内存属性，所以并不能做到高效的算法，不能保证性能，但是好在swift是一门支持多编程范式的语言，在合适的地方使用合适的方法才是我们需要去做的。
参考资料
http://www.developcls.com/qa/fd85d33e01534c788c3cb4b4d1704af7.html
网友评论