Lich Ray写了个帖子《
函数式编程语言曲高和寡?》, 用快速排序的例子来说明函数式编程在表达思想方面比命令式语言更容易,其实这一点毋庸置疑,如果你正在读或者读过SICP的话。文中给了haskell、 scheme和javascript的实现例子,我也凑趣写了个Erlang版本,haskell我不了解就不说了,其他实现分别如下:
scheme:
ruby 代码
- (define (qsort ls)
- (if (null? ls) '()
- (let
- ((x (car ls))
- (xs (cdr ls)))
- (let
- ((lt (filter (lambda (y) (< y x)) xs))
- (st (filter (lambda (y) (>= y x)) xs)))
- (append (qsort lt) (list x) (qsort st))))))
javascript:
js 代码
-
- Array.prototype.head = function () {
- return this[0];
- }
-
- Array.prototype.tail = function () {
- return this.slice(1);
- }
-
- Array.prototype.filter = function (proc) {
- var tmpArr = [];
- for (var i = 0; i < this.length; i++)
- if (proc(this[i]) == true)
- tmpArr.push(this[i]);
- return tmpArr;
- }
- Array.prototype.qsort = function () {
- if (this == false) return []
- var x, xs, lt, st
- x = this.head()
- xs = this.tail()
- lt = xs.filter(function (y) {return y < x})
- st = xs.filter(function (y) {return y >= x})
- return lt.qsort().concat([x], st.qsort())
- }
用Erlang的话,Erlang的list其实跟scheme的list是一样的,甚至连定义的基本高阶函数都一样:map,filter,append等等,利用lists模块提供的filter和append,我们可以写出:
ruby 代码
- qsort([])->[];
- qsort([H|T])->
- Lt=lists:filter(fun(E)->Eend,T),
- St=lists:filter(fun(E)->E>=H end,T),
- lists:append(qsort(Lt),lists:append([H],qsort(St))).
我们来比较下scheme和Erlang版本,两者最显著的不同是,scheme使用了条件语句if,而Erlang却是通过模式匹配来代替条件分支判 断。同样,在list的分解上面,Erlang也是利用了规则匹配来代替car,cdr函数,从这里可以看出规则匹配在Erlang中的主要作用:分解复 杂数据结构以便赋值和条件分支的分派。
扯远些可以谈到模式匹配是以“like-a”来代替消息分派在传统命令式语言中严格的“is-a”,这也跟现实世界的情况更为符合,现实世界中我们对事物 的判断都是模糊。而这一点,不正是“Duck-Typing”?传统语言对于对象的类型(type)判断来源于严格确定对象是什么类(class),不是 这个类它就没有相应的方法,而事实上类与类型这两个概念并不是一致的,对象的类型更应该根据对象能够做什么来决定。这只是我读《失踪的链环》 得来的感受,如果对模式匹配还有怀疑的话,让我们回到这个例子的Erlang版本,代码中我们调用了两次filter进行全表扫描,以便得到根据H切割的 大小两个部分,这在性能上有不小的影响,那么我们能不能只进行一次全表扫描呢,返回结果是“大小”两个部分,看看Erlang应该怎么写:
ruby 代码
- sort([]) -> [];
- sort([Pivot|Rest]) ->
- {Smaller, Bigger} = split(Pivot, Rest),
- lists:append(sort(Smaller), [Pivot|sort(Bigger)]).
- split(Pivot, L) ->
- split(Pivot, L, [], []).
- split(Pivot, [], Smaller, Bigger) ->
- {Smaller,Bigger};
- split(Pivot, [H|T], Smaller, Bigger) when H < Pivot ->
- split(Pivot, T, [H|Smaller], Bigger);
- split(Pivot, [H|T], Smaller, Bigger) when H >= Pivot ->
- split(Pivot, T, Smaller, [H|Bigger]).
这几行代码充分展现了模式匹配的威力,不过Erlang其实有内置的方法partition用于切割list的,这里只是为了展现模式匹配,因此上面的代码可以改为:
ruby 代码
- sort([]) -> [];
- sort([Pivot|Rest]) ->
- {Smaller, Bigger} = lists:partition(fun(E)->Eend, Rest),
- lists:append(sort(Smaller), [Pivot|sort(Bigger)]).
同样的代码改写为ruby版本:
ruby 代码
- def qsort(arr)
- if arr==[]
- []
- else
- x=arr.shift
- smaller,bigger=arr.partition{|e| e<=x}
- qsort(smaller)+[x]+qsort(bigger)
- end
- end
ruby与Erlang都有并行赋值,但是ruby不支持模式匹配。请注意ruby并没有尾递归优化,因此上面的代码在数组比较大的时候会导致栈溢出,想用ruby做函数式编程应该尽量多使用循环和map,filter,collect等辅助高阶函数。
另外一个Erlang与ruby、scheme比较重要的区别是Erlang的变量只能赋值一次(或者说绑定),也就是single assignment。这个特点与Erlang所要满足的运行场景有紧密关系,当系统发生错误时,就可以从原来的值重新启动任务,而不用担心由于变量值的 变化导致系统恢复困难。
分享到:
相关推荐
scheme语言structure数据类型的使用例子,使用方法参阅我的博文http://blog.csdn.net/tumiz/article/details/27852349
Ruby Ruby中的一个小型Scheme实现
scheme-lib scheme-lib 是一个scheme使用的库。目前支持android,其它平台在规划中。
Intent scheme url的引入虽然带来了一定的便捷性,但从另外一方面看,给恶意攻击页面通过intent-based攻击终端上已安装应用提供了便利,尽管浏览器app已经采取了一定的安全策略来减少这一类风险,但显然是不够的。...
抓取scheme协议.js
手机中的APP都有一个沙盒,APP就是一个信息孤岛,相互是不可以进行通信的。但是iOS的APP可以注册自己的URL Scheme,URL Scheme是为方便app之间互相调用而设计的。我们可以通过系统的OpenURL来打开该app,并可以传递...
Android中的Scheme是一种页面内跳转协议,通过自定义Scheme协议,可以跳转到app中的任何页面。 服务器可以定制化跳转app页面 app可以通过Scheme跳转到另一个app页面 可以通过h5页面跳转app原生页面
GoScheme - 只是用Go编写的另一个Scheme解释器
Scheme是LISP的一个重要变种,这个是它在Windows环境下的一个安装程序。愿与对LISP感兴趣的朋友共享。
scheme方式实现唤醒外部app 支持webview,浏览器链接地址 支持app唤醒目标app
文档的内容为 快手应用的一些 scheme跳转信息,我们可以在自己的应用内部直接唤起快手的指定界面,无论是从H5还是原生界面,包括直接跳转到某用户的主页,直接与某用户发起对话等
JSchemeMin 是一个JVM平台上的Scheme语言实现。作为R7RS的实现,JSchemeMin支持Scheme的所有标准特性,包括头等公民地位的过程、尾递归优化、继续、用户定义记录、库(包括R7RS附录A中全部语法和过程,不只base)、...
收集的用scheme语言编写的八皇后的解法,对学习scheme语言想理解递归的同志们是一个好例子,sicp中也有此练习题。
scheme语言相关的学习资料: guide_racket_scheme.pdf Lisp之根源.pdf Racket图文教程.pdf scheme-primer.pdf schem-r5rs_cn.pdf The_Little_Schemer.pdf 通过Scheme看函数式编程.pdf Write_Yourself_a_Scheme_in_48...
使用shceme跳转支付宝指定页面,从支付宝APK提取出来,key的数字就是scheme的said,自行替换即可,json里有部分是之前的支付宝的活动页面,跳转了会提示已暂停服务 //扫一扫 alipayqr://platformapi/startapp?saId=...
android:scheme 通过uri跳转到APP应用指定Activity
scheme源代码scheme 阴阳题源代码
一个用javascript实现的scheme解释器,可以运行在浏览器中或node.js中。 刚刚看到编译原理与实践第二章,一时兴起,想写个以前就想写的scheme的解释器。昨天晚上开始写,到刚才为止,接近一天的时间。把一时的...
The scheme programming language 4th 关于Scheme语言的书,值得一看