浅谈Swift中的函数式

对于一个数学专业毕业的学生,函数式编程天然的吸引力了我,从哥德尔的不完备定理,到邱奇的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

纯函数数据结构

函数式 Swift

康托尔、哥德尔、图灵——永恒的金色对角线

函数式编程的早期历史

Functor、Applicative 和 Monad

Haskell

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,875评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,569评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,475评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,459评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,537评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,563评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,580评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,326评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,773评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,086评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,252评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,921评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,566评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,190评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,435评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,129评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,125评论 2 352

推荐阅读更多精彩内容