函数式编程思维小例(一)

Functional thinking with examples in F# I

原创:顾远山
著作权归作者所有,转载请标明出处。

笔者最近在重读Neal Ford所著的《函数式编程思维》,相比五年前走马观花般略读,这次确有更深体会。原书列举了大量例子,基本上涵盖Java、Groovy、Scala和Clojure等语言,然而美中不足的是,作者和译者都没涉及.NET,更别提针对F#展开了。笔者针对原书第三章《权责让渡》,简辅以F#语言数例(非原例),仅当读书笔记,亦方便其他由命令式编程转函数式编程的开发者参考思路,望抛砖引玉,共同进步。

原书提到“函数式思维的好处之一,便是能把低层次细节的控制权移交运行时,从而消弭一大批注定会发生的程序错误。”另外,书中阐述了“五种向语言和运行时让渡控制权的途径,让开发者抛开负累,投入到更有意义的问题中去”。

迭代让位于高阶函数

对于传统的命令式编程,迭代(或循环)是主要的控制过程,通常由for代码块实现,在C系语言中作为循环控制几乎无处不在,借用C#举例,遍历某个一维整型数组,并把所有元素的按行输出到控制台,代码如下:

var array = new [] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for(int i = 0; i < array.Length; i++)
{
    System.Console.WriteLine($"{array[i]}");
}

上述代码展现了迭代过程如何实现——引入一个名为i的局部变量作为计数器,设定其初始值为0,目标值为array.Length - 1,每步迭代后计数器递增幅度为1,而具体功能的实现则被放进{ ... }代码块内。

函数式编程的思维则把迭代的实现抽象出来交给运行时,让开发者利用高阶函数直入主题进行具体功能的实现。这种方式在大部分只需要做简单遍历的场景是极其便利的,开发者无需关心迭代过程中的计数器,尤其对于嵌套循环(一堆对ijkl的组合操作直叫人眼花缭乱失之毫厘差之千里),从而聚焦具体功能,省时省力且不易出错。

不妨用F#重写刚才的例子,如下:

[|1..10|] |> Array.iter (printfn "%d")

上述代码使用了高阶函数Array.iter来实现迭代,计数器(初始值、目标值和步增幅度等)对于开发者而言完全是透明的。

到这里,有开发者也许会问,你用一个函数把原先用来实现迭代过程的计数器都封装起来了,但凡迭代就是千篇一律逐个元素遍历,操纵不了计数器岂不是意味着要放弃对迭代的灵活性?比如我不想从第一个元素开始,又如我不想到最后一个元素截止,或如我不想逐个而是跳跃遍历等……这些问题很实际,不过无须担心,函数式编程语言发展到现在,内建的很多高阶函数都可以控制迭代过程,它们形式相似但功能各异,足以应对现实中的复杂场景,实际上比传统的计数器更强大。

接下来我们会针对F#中用以控制迭代过程常用的高阶函数逐个进行举例。

iter

*.iter相当于最基本的迭代了,函数名来自“迭代”对应英文单词iterate的简写,顾名思义就是对某个数据结构里的所有元素从头到尾逐个进行遍历,而且仅遍历,即遍历过程中对每个元素的单元操作不返回值。

不止列表类型List,F#中内置的其他Collection类型,包括数组类型Array、序列类型Seq(对应.NET其他语言的IEnumerable<T>)、字典类型Map和集合类型Set,都支持iter这个高阶函数。其实你去Bing上搜索一下Microsoft.FSharp.Collections直达MSDN,会发现更多惊喜,简列表格如下:

Function List Array Seq Map Set
iter O(N) O(N) O(N) O(N) O(N)
iteri O(N) O(N) O(N) - -
iter2 O(N) O(N) O(N) - -
iteri2 O(N) O(N) - - -

除了iter函数之外,F#还提供了iteriiter2iteri2三个函数进行元素遍历,简直都快玩出花来了。不妨简单看看它们的签名,如下:

F#中的*.iter*函数

其余三个函数具体用法与iter相差无几,MSDN也有详例,本文就不再赘述了。

map

*.map函数可能是函数式编程中最常用的高阶函数了,函数名本身直接取自“映射”的英文单词map,开发者可以使用map函数在对Collection类型进行迭代的同时对其中的元素进行映射(施行变换)。

F#简例如下:

[1..10] |> List.map (pown 2)

输出的结果是一个整型列表,其中每个元素分别为2的1次幂、2次幂……10次幂:

[2; 4; 8; 16; 32; 64; 128; 256; 512; 1024]

若想得到的整型列表中每个元素值为原元素值的平方,只需对传入List.map的函数稍作调整即可,如下:

[1..10] |> List.map (fun n -> pown n 2)

造成这个有趣结果的原因是F#中内建的pown函数的第一个参数为底,第二个参数才是幂。

回到正题,如果对比itermap函数的签名:

  • List.iter: ('a -> unit) -> list<'a> -> unit
  • List.map: ('a -> 'b) -> list<'a> -> list<'b>
    我们会发现这两个函数非常相似,某种程度上可以理解成iter相当于map'bunit情况下的一个特例,只是结果把list<unit>约简为unit罢了。

reduce/fold

归约函数reduce和折叠函数fold在函数式编程中也被高频使用,它们的功能也非常通俗易懂,就是把一堆元素以某种方式揉在一起变成一个元素,至于某种方式具体是哪种方式,开发者可以通过函数的形式把它作为参数传入其中。最常见的例子(没有之一)就是求和,诸如对一个整型列表里所有的元素求和,用F#的reduce函数很方便就能实现,如下:

[1..10] |> List.reduce (+)

fold函数实现则需要多传入一个作为初始状态的参数,如下:

[1..10] |> List.fold (+) 0

上面的代码纵然可行,但会被Visual Studio Code + ionide 框架里鄙视,F# Linter会友善地提醒你,这段代码可以直接用List.sum进行重构,而List.sum函数,恰好就是求和函数。

refactor reminding

求和也许不是个有说服力例子,但它肯定不是唯一的例子——要是reducefold函数只能用来求和,那未免有点太弱了。函数式编程的强大之处恰好在于函数,在F#中,函数是头等公民,函数可以直接作为参数传入其他高阶函数,求和的例子,被传入的函数为(+),倘若要求积,只需要把+改成*即可。无论如何,只要你能把糅合的规则用某个函数定义清楚,reducefold函数就能帮你把这堆元素糅合成一个元素,美其名曰“归约”或“折叠”。

不妨再举个例子:把一组英文单词,以空格为分隔符,按顺序组成句子。这一看就是典型的归约问题,给定一个字符串列表,通过指定规则,对列表中的字符串逐个迭代并归约成一个字符串,用F#简单实现,如下:

//using reduce
["Time";"and";"tide";"wait";"for";"no";"man"] |> List.reduce (sprintf "%s %s")
//using fold
["Time";"and";"tide";"wait";"for";"no";"man"] |> List.fold (sprintf "%s %s") ""
//result
val it : string = "Time and tide wait for no man"

通过上面的例子,我们可以发现reducefold两个函数也是高度相似,那它俩的区别是什么呢?还是直接对比函数签名吧:

  • List.reduce: ('a -> 'a -> 'a) -> list<'a> -> 'a
  • List.fold: ('a -> 'b -> 'a) -> 'a -> list<'b> -> 'a

这两个函数虽然都是把一堆元素糅合从一个元素,但从函数签名看,foldreduce要灵活更多。首先,最直观的是类型不一样,fold函数可以把一堆既定类型的元素糅合成一个其他类型的元素,而reduce函数只能把一堆既定类型的元素糅合成相同类型的元素。其次,fold函数可以指定不依赖于这一堆元素的初始状态,而reduce函数没有所谓的初始状态。某种程度上可以理解成reduce相当于fold'b'a情况下的一个特例,只是初始状态为'a类型的零值罢了。此处的“零值”因类型而异,如整型的零值是0,字符串类型的零值是"",是可以参与计算的有效值,跟null是两码事。

举个类似的例子更直接地展现二者的区别,如把某个字符类型的列表折叠为一个字符串,如下:

//using fold, OK
['F';'u';'n';'c';'t';'i';'o';'n';'a';'l'] |> List.fold (sprintf "%s%c") ""
//result
val it : string = "Functional"
//using reduce, KO
['F';'u';'n';'c';'t';'i';'o';'n';'a';'l'] |> List.reduce (sprintf "%c%c") 
//result
error FS0001: Type mismatch. Expecting a
    'char -> char -> char'
but given a
    'char-> char -> string'
The type 'char' does not match the type 'string'

对于这个例子:如果直接使用fold函数,你会得到一个预期的结果;要是直接使用reduce函数,你会得到的只能是一个意外的错误。原因在报错信息里写得很清楚——“类型不匹配”。charstring是两种不同的数据类型,硬套reduce函数是不合理的,若非要用,可以先用map统一类型,如下:

//using map then reduce, OK
['F';'u';'n';'c';'t';'i';'o';'n';'a';'l'] |> List.map string |> List.reduce (sprintf "%s%s")
//result
val it : string = "Functional"

很多人或多或少知道mapreduce是好搭档,但不是所有人都知其所以然,而上例正好完美演绎了它们如何相得益彰。要是觉得效果还不够明显,我们可以再来一遍,如下:

//using map then reduce, OK, OK
[70; 117; 110; 99; 116; 105; 111; 110; 97; 108]
|> List.map (char >> string)
|> List.reduce (sprintf "%s%s")
//result
val it : string = "Functional"

map负责转换,reduce负责归约,两者各司其职,配合得天衣无缝。

filter

个人以为*.filter是函数式编程思维中最最最直白的高阶函数了,就算你没有任何IT背景,不懂iter,不懂map,不懂reduce代表什么,你不可能不知道filter是什么意思。对,它就是那个意思。这个函数需要一个返回布尔类型的函数作为判断条件输入,才能对给定的Collection类型进行筛选。筛选也是极其常见的操作,比如在一个整型列表中,把小于5的所有元素筛选出来,可用F#实现如下:

[1..10] |> List.filter ((>) 5)

特别提醒:上例中,>本身是操作符,但(>)被表示为函数,类型为'a -> 'a -> bool,其中函数的第一个参数为其左操作数,第二个参数为其右操作数,所以代码块x > y的等价代码块是(>) x y。所以,当我们需要筛选小于5的元素,我们需要传入的判断条件函数应为fun n -> 5 > n,等价于fun n -> (>) 5 n,柯里化后就变成了(>) 5。关于函数式编程中的柯里化应用,笔者在本系列的后续小例中会展开细论。

小结

本文针对《函数式编程思维》第三章《权责让渡》的第一种途径——迭代让位于高阶函数,用F#语言列举了几个例子,展示了在函数式编程过程中,抛开for循环,借用Collection类型的高阶函数同样可以实现迭代逻辑的处理,涉及的场景包括:

  • iter
  • map
  • reduce/fold
  • filter
    当然,F#中Collection类型的高阶函数还有很多,光fold函数也还有另外三兄弟fold2foldBackfoldBack2,足以见得函数式编程语言针对不同的场景内建了极为丰富的高阶函数选择,而且通常都经过了运行时优化,大部分情况下,它们比开发者自己随手写的for性能要更高,大可放心使用。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,602评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,442评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,878评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,306评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,330评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,071评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,382评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,006评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,512评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,732评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,283评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2 345

推荐阅读更多精彩内容