泛函编程(2)-初次体验泛函编程

    泛函编程和数学方程式解题相似;用某种方式找出问题的答案。泛函编程通用的方式包括了模式匹配(pattern matching)以及递归思维(Recursive thinking)。我们先体验一下:(在阅读本系列文章之前,相信读者已经对Scala语言及REPL用法有所了解了。在这就不去解释Scala的语法语意了。)

先来个简单的:

1 def reportError(msgId: Int): String = msgId match {
2      | case 1 => "Error number 1."
3      | case 2 => "Error number 2."
4      | case 3 => "Error number 3."
5      | case _ => "Unknown error!"
6      | }
7 reportError: (msgId: Int)String

很明显,这个函数的是一个纯函数,也是一个完整函数。因为函数主体涵盖了所有输入值(注意: case _ =>)。我们可以预知任何输入msgId值所产生的结果。还有,函数中没有使用任何中间变量。看看引用情况:

1 reportError(2)
2 res3: String = Error number 2.
3 
4 scala> reportError(-1)
5 res4: String = Unknown error!

恰如我们预测的结果。

再来看看一个递归(Recursion)例子:阶乘(Factorial)是一个经典样例:

1 def factorial(n: Int): Int = {
2       if ( n == 1) n
3       else n * factorial(n-1)
4   }                                               //> factorial: (n: Int)Int
5   factorial(4)                                    //> res48: Int = 24

也可以用模式匹配方式:

1 def factorial_1(n: Int): Int = n match {
2       case 1 => 1
3       case k => k * factorial(n-1)
4   }                                               //> factorial_1: (n: Int)Int
5   factorial_1(4)                                  //> res49: Int = 24

用模式匹配方式使函数意思表达更简洁、明了。

我们试着用“等量替换”方式逐步进行约化(reduce)

1 factorial(4)
2   4 * factorial(3)
3   4 * (3 * factorial(2))
4   4 * (3 * (2 * factorial(1)))
5   4 * (3 * (2 * 1)) = 24

可以得出预料的答案。

递归程序可以用 loop来实现。主要目的是防止堆栈溢出(stack overflow)。不过这并不妨碍我们用递归思维去解决问题。 阶乘用while loop来写:

1 def factorial_2(n: Int): Int = {
2          var k: Int = n
3          var acc: Int = 1
4          while (k > 1) { acc = acc * k; k = k -1}
5          acc
6   }                                               //> factorial_2: (n: Int)Int
7   factorial_2(4)                                  //> res50: Int = 24

注意factorial_2使用了本地变量k,acc。虽然从表达形式上失去了泛函编程的优雅,但除了可以解决堆栈溢出问题外,运行效率也比递归方式优化。但这并不意味着完全违背了“不可改变性”(Immutability)。因为变量是锁定在函数内部的。

最后,也可用tail recursion方式编写阶乘。让编译器(compiler)把程序优化成改变成 loop 款式:

1 def factorial_3(n: Int): Int = {
2     @annotation.tailrec
3       def go(n: Int, acc: Int): Int = n match {
4           case 1 => acc
5           case k => go(n-1,acc * k)
6       }
7       go(n,1)
8   }                                               //> factorial_3: (n: Int)Int
9   factorial_3(4)                                  //> res51: Int = 24

得出的同样是正确的答案。这段程序中使用了@annotation.tailrec。如果被标准的函数不符合tail recusion的要求,compiler会提示。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏真皮专栏

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

682
来自专栏我杨某人的青春满是悔恨

“身首异处”的序列(Swift)

声明:文章开头部分内容翻译自objc的一篇博客。当然,我并没有逐行翻译原文,只是说个大致意思,顺带阐述一些自己的理解和扩展思考,还有我自己的代码。

1052
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之为用于高考名次排序的排序算法

  在高考结束以后,所有人都在等着成绩,政府部门面对几百万的数据,你知道他们是怎么算名次的么?上一次学到递归排序以及快排,确实,用他们可以实现,可是他们的时间复...

391
来自专栏racaljk

探索C++对象模型

只说C++对象模型在内存中如何分配这是不现实的,所以这里选择VS 2013作为调试环境具体探讨object在内存中分配情况.目录给出了具体要探讨的所有模型,正...

823
来自专栏淡定的专栏

正则表达式 : 检索匹配的利器

正则表达式是开发中一个不可多得的利器,本文旨在帮助大家入门正则并学会解决常见的正则问题,希望能帮到大家。

1230
来自专栏blackheart的专栏

[程序设计语言]-[核心概念]-03:控制流

0.概述 前面介绍了语言的演进以及一些基础概念后,从本篇开始进入了语言的核心问题中。这一篇讨论的是语言计算模型(大致可以用控制流来表述),大致如下7种: 顺序执...

18910
来自专栏王肖的UT

正则表达式~~检索匹配的利器

正则表达式(Regular Expression,下文简称为Regular或正则)是开发中一个不可多得的利器,它广泛应用于字符串的查找、匹配以及替换等场景。以...

4947
来自专栏青青天空树

说反话(c++实现)

输入:测试输入包含一个测试用例,在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由英文字母(大小写有区分)组成的字符串,单词之间...

592
来自专栏编程之旅

数据结构——无权图的路径问题(C++和java实现)

好像又是接近半个月没有更新,这半个月忙着结婚的各项事情,本来预计的学习任务也拖拖拉拉,进度缓慢。吐槽一句,拍婚纱照真的是最非常非常累的一件事情,不想再有下次了。

832
来自专栏彭湖湾的编程世界

【算法】哈希表的诞生

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

32910

扫码关注云+社区