泛函编程(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 条评论
登录 后参与评论

相关文章

来自专栏Crossin的编程教室

【Python 第24课】 if的嵌套

和for循环一样,if也可以嵌套使用,即在一个if/elif/else的内部,再使用if。这有点类似于电路的串联。 if 条件1: if 条件2: ...

2846
来自专栏IT可乐

深入理解计算机系统(4.1)------Y86指令集体系结构

  本章我们将进入处理器体系结构介绍的神秘海洋中,我们熟悉的手机,电脑等设备的核心硬件都离不开处理器。处理器可以称的上是人类创造的最复杂的系统之一,一块手指大小...

20110
来自专栏IT可乐

深入理解计算机系统(2.1)------信息的存储和表示

  前面我们介绍了《深入理解计算机系统》第一章的内容----计算机系统漫游。包括简单介绍了 Hello World 程序在计算机中是如何运行的,存储设备的层次结...

1868
来自专栏PPV课数据科学社区

【学习】数据分析师的Python日记-第1天:谁来给我讲讲Python?

今天带来的是PYTHON,这是一篇非常有意思的文章。希望对大家有帮助。 ---- ---- 导语:或许是网上嘈嘈杂杂的关于大数据、互联网的新形势争论,或许是招聘...

1899
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题14调整数组顺序使奇数在偶数之前

本题详细解析都已在代码中注释了: /** * 题目:输入一个数组,要求将奇数放在数组的前半段,偶数放在数组的后半段 * @author 大闲人柴毛毛 *...

2845
来自专栏owent

“C++的90个坑”-阅读笔记

C++确实是一门复杂的语言。包括之前查看了一些C++11的文档和做了一些实践和总结,越来越觉得C++是门神奇的语言,也是个陷阱多多的语言。 我现在开发过程中最...

491
来自专栏自动化测试实战

接口测试基础——第7篇 简单的Python知识普及(二)之装饰器

41614
来自专栏一个会写诗的程序员的博客

13.11 Scala混用Java的集合类调用scala的foreach遍历问题13.11 Scala混用Java的集合类调用scala的foreach遍历问题问题描述原因分析解决方案

由于都运行在JVM上,Java与Scala之间基本能做到无缝的集成,区别主要在于各自的API各有不同。由于Scala为集合提供了更多便捷的函数,因此,Java与...

494
来自专栏余林丰

Java IO(1)基础知识——字节与字符

  正所谓怕什么来什么,这是知名的“墨菲定律”。Java基础涵盖各个方面,敢说Java基础扎实的人不是刚毕业的学生,就是工作N年的程序员。工作N年的程序员甚至也...

1869
来自专栏deepcc

javascript 面向对象技术

3227

扫码关注云+社区