文档章节

Scala函数式编程原则 Week-2

MoonSugar
 MoonSugar
发布于 2016/07/20 00:58
字数 1419
阅读 69
收藏 0

#尾递归 在计算函数 f(e1, ..., en)时,由于Scala采用class-by-value的模式,所以首先会计算函数参数e1, ..., en,将参数的计算结果v1, ..., vn带回到函数 f()中。 对比以下两个函数 gcd()计算两个整数的最大公约数,和 factorial()斐波那契函数。

def gcd(a: Int, b: Int): Int = 
    if (b == 0) a else gcd(b, a % b)

def factorial(n: Int): Int = 
    if(n == 0) 1 else n * factorial(n - 1)

对 gcd(14, 21)函数按照call-by-value的方式计算:

gcd(14, 21)
→ if (21 == 0) 14 else gcd (21, 14 % 21)
→ if (false) 14 else gcd (21, 14 % 21)
→ gcd(21, 14 % 21)
→ gcd(21, 14)
→ if (14 == 0) 21 else gcd (14, 21 % 14)
→ gcd (14,  7)
→ gcd (7, 0)
→ if (0 == 0) 7 else gcd (0, 7 % 0)
→ 7

计算factorial函数:

factorial(4)
→ if (4 == 0) 1 else 4 * factorial(4 - 1)
→ 4 * factorial(3)
→ 4 * (3 * factorial(2) )
→ 4 * (3 * (2 * factorial(1)) )
→ 4 * (3 * (2 * ( 1 *  factorial(0))) )
→ 4 * (3 * (2 * (1 * 1) ) )
→ 120

在计算 gcd()函数的时候,每次递归都是调用函数的最后一部分,并且不包含前一次递归的内容。而 factorial()在每次递归时,都会包含前一次递归中的信息。前一种递归方式被称为“尾递归”(tail recursion),函数在每一次调用过程中都只调用了自己最后一步的操作,这是函数就可以复用其栈。通常来说,如果一个函数的最后一步操作是调用一个函数(这个函数可以是其本身),那么一个栈帧(stack frame)就实现所有的调用,这就叫做尾调用。

现在,我们将factorial()函数改写为tail-recursion的模式

def factorial(n: Int): Int = {
    def loop(acc: Int, n: Int): Int  = {
         if (n == 0) acc
         else loop( acc * n, n - 1 )
    }
    loop(1, n)
}

#高阶函数

在数学和计算机科学中,高阶函数是至少满足下列一个条件的函数:

  • 接受一个或多个函数作为输入
  • 输出一个函数 在数学中高阶函数也叫做算子(运算符)或者泛函,常见的例子就是微积分中的导数。在无类型lambda演算,所有函数都是高阶的;在有类型lambda演算(大多数函数式编程语言都从中演化而来)中,高阶函数一般是那些函数型别包含多于一个箭头的函数。在函数式编程中,返回另一个函数的高阶函数被称为Curry化的函数。

##函数作为参数

 def sum(f: Int => Int, a: Int, b: Int): Int = 
    if (a > b ) 0
    else f(a) + sum(f,  a + 1 ,  b)

def sumInts(a: Int, b: Int): Int = sum(id,  a,   b)
def sumCubes(a: Int, b: Int): Int = sum(cube, a,  b)

def id(x: Int): Int =  x
def cube(x:   Int): Int = x * x * x

函数 sum()就是一个高阶函数,它接受一个函数作为参数,并且要求这个函数要接受一个整数作为参数,最后返回一个整数。 “A => B” 声明了一个函数的类型,这个函数接受一个类型A的参数,并且返回一个类型B的值。

##匿名函数 为了简洁Scala的语法,Scala提供了匿名函数,我们将上面例子的 sumInts()和 sumCubes()函数改用匿名函数的方法表示:

def sumInts(a: Int, b: Int): Int = sum(x => x, a,  b)

def sumCubes(a: Int, b: Int): Int = sum(x => x * x * x, a,  b)

##柯里化(Currying)

把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数而且返回结果的新函数的技术。 Currying的动机: 由于数学中的一些分析技巧只能应用于接受一个参数的函数,而大部分函数都接受不止一个值作为参数,Currying使得这些分析技巧能够被应用到所有能Currying的函数上。

而在计算机科学上Currying提供了一个在简单理论模型中研究多参函数的方法(例如只接受一个参数的λ演算模型); Currying使函数表达更加简洁。

好,我们现在再次改写 sum()函数,使其柯里化。

 def sum(f: Int => Int):  (a: Int, b: Int) => Int  =  {
    def sumF(a: Int,  b: Int): Int =  
        if (a  >   b)  0
        else f(a) + sumF(a + 1,  b)
    sumF
}
    

这次我们在 sum()函数中定义了一个 sumF()函数,并将其作为 sum()函数的返回值,同时我们也声明了 sum()的返回类型为 (a: Int, b: Int) => Int,接受两个整型作为参数并返回一个整型的函数。 接下来我们再根据新的 sum()函数,修改 sumInts()和 sumCubes()

def sumInts =  sum(x => x)
sumInts(5, 6)  // 调用方式不发生改变

def sumCubes = sum(x => x * x * x)
sumCubes (5, 6)  // 调用方式不发生改变

现在新的 sumInts()和 sumCubes()是不是要比以前简洁多了呢?其实我们还可以直接跳过 sumInts(), sumCubes()这些中间函数,利用我们最开始定义的 id(), cube()来实现函数的调用。

sum(cube)(1, 10)  ==  (sum(cube))(1, 10)

由于定义一个返回函数的函数在函数式编程中太有用了,Scala专门提供了语法糖支持,利用语法糖可以对 sum()进行如下改写:

def sum(f: Int  =>  Int)(a: Int, b:  Int): Int = 
    if (a  >  b)  0 else f(a) + sum(a + 1, b)

我们现在Currying推广到拥有n个参数的情况:

def f(args_1)...(args_n) = E
// 当 n > 1 时
→ def f(args_1)...(args_n-1) = { def g(args_n) = E; g }
// 匿名化函数 g()
→ def f(args_1)...(args_n-1) = { args_n => E }
// 在对args_n-1重复上述步骤
→ def f(args_1)...(args_n-2) = { args_n-1 => (args_n => E) }
 .
 .
 .
→ def f = (args_1 => (args_2 => ...(args_n => E)))

© 著作权归作者所有

MoonSugar
粉丝 0
博文 12
码字总数 20196
作品 0
海淀
程序员
私信 提问
Scala 的学习笔记系列(持续更新中)

最近学习 Scala,因它是灵活的函数式编程,还有就是能为 PlayFramework 2.0 服务,看的是 《Programming in Scala》 那本书,并记下自己认为值得记录的东西,列举 Scala 用元组/列表类型实现...

YanbinQ
2012/10/26
0
1
scala入门之识别函数式风格

scala允许指令式的编程风格,但是鼓励采用函数式的风格。如果你是从指令式的背景转到scala来的-----例如,如果你是Java程序员------那么学习scala将面对的主要挑战就是理解怎样用函数式的风格...

柳哥
2014/06/05
0
0
Scala的协变covariant(+),逆变contravariant(-),上界(:)

原文:https://my.oschina.net/xinxingegeya/blog/486671 Scala的协变(+),逆变(-),上界(<:),下界(>:) 协变covariant、逆变contravariant、不可变invariant 对于一个带类型参数的类型,比如...

u013063153
2017/11/09
0
0
Scala的协变(+),逆变(-),上界(:)

Scala的协变(+),逆变(-),上界(<:),下界(>:) 协变covariant、逆变contravariant、不可变invariant 对于一个带类型参数的类型,比如 List[T],如果对A及其子类型B,满足 List[B]也符合List[...

秋风醉了
2015/08/02
0
0
Scala之初步认识与环境准备

了解 Scala 1.1. 什么是 Scala Scala 是 Scalable Language 的简写,是一门多范式的编程语言。 Scala设计的初衷是要集成面向对象编程和函数式编程的各种特性。Scala运行于Java平台(Java虚拟...

飞鱼说编程
2018/12/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

“旧城改造”的背后——银泰新零售阿里云解决方案(上)

相关免费课程《银泰新零售上云解决方案精讲》上线中 立足实战 讲透经典案例 助你快速理解新零售 第一节学习地址 第二节学习地址 传统线下商业体上云的案例 与其说银泰上云,倒不如说银泰“旧...

阿里云官方博客
29分钟前
2
0
记一次升级Oracle驱动引发的死锁

问题描述 近期项目需要从虚拟机环境迁移到容器环境,其中有一个项目在迁移到容器环境之后的两天之内出现了2次“死锁(deadlock)”的问题,部分关键日志如下: Found one Java-level deadlock:...

ksfzhaohui
31分钟前
14
0
MySQL 中的 information_schema 数据库

欢迎查看原文 - 本博客仅记录 https://blog.csdn.net/kikajack/article/details/80065753 -- 是否开启bin_log日志: off为关闭-- show variables like 'log_%'; show variables like '......

莫库什勒
39分钟前
1
0
Random在高并发下的缺陷以及JUC对其的优化

Random可以说是每个开发都知道,而且都用的很6的类,如果你说,你没有用过Random,也不知道Random是什么鬼,那么你也不会来到这个技术类型的社区,也看不到我的博客了。但并不是每个人都知道...

编程SHA
44分钟前
2
0
T5大牛带你解析:如何实现分布式技术

1.分布式事务 2. 分布式锁 Java 原生 API 虽然有并发锁,但并没有提供分布式锁的能力,所以针对分布式场景中的锁需要解决的方案。 分布式锁的解决方案大致有以下几种: 基于数据库实现 基于缓...

李红欧巴
56分钟前
35
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部