函数式程序设计语言.ppt

2020年1月26日星期日 程序设计语言范型ProgrammingLanguagesParadigms 教师 张荣华计算机科学与技术学院华北电力大学 函数式程序设计语言 Scheme语言数据抽象 第二部分 第五章 Scheme语言数据抽象 第五章 3 回顾 任何强有力的程序设计语言都必须能表述基本的数据和过程 还需要提供对数据和过程进行组合和抽象的方法 摘自 计算机程序的构造和解释 控制抽象 表达式层次 语句层次 程序单元层次 数据抽象 本章研究内容 Scheme语言数据抽象 第五章 4 回顾 Scheme语言控制抽象 第五章第二部分 将一个过程的使用方式 与该过程究竟如何通过更基本的过程实现的具体细节相互分离的一种技术 基本数据 数 基本过程 算数运算 用复合 条件 参数将过程组合起来形成复合过程 通过define lambda做过程抽象 过程的计算模式 递归计算和迭代计算过程 高阶过程Scheme语言数据抽象 第五章第三部分 讨论程序设计语言提供的将数据对象组合起来形成复合数据的方式 Scheme语言数据抽象 第五章 5 内容 1 数据抽象导引1 1序对1 2有理数包的抽象屏障2 表结构2 1序列与闭包性质2 2表操作2 3表映射3 函数式语言高级抽象综合实例 Scheme语言数据抽象 第五章 6 1 数据抽象导引 数据抽象将程序中处理数据对象的表示的部分 与处理数据对象的使用的部分相互隔离起来的一种技术 例如 考虑线性组合 ax by define linear combinationabxy ax by define linear combinationabxy add mulax mulby 数据抽象的关键 构造函数 粘合剂 选择函数 分离剂 Scheme语言数据抽象 第五章 7 实例 有理数的算术运算 假定 存在一种方法可以从分子和分母构造出有理数 存在一种方法可以从已经存在的有理数中分离它的分子和分母 make rat numer denom 从分子n和分母d构造有理数并返回 返回有理数x的分母 返回有理数x的分子 构造函数 选择函数 Scheme语言数据抽象 第五章 8 实例 有理数的算术运算 例如 实现两个有理数相加 Scheme语言数据抽象 第五章 9 内容 1 数据抽象导引1 1序对1 2有理数包的抽象屏障2 表结构2 1序列与闭包性质2 2表操作2 3表映射3 函数式语言高级抽象综合实例 Scheme语言数据抽象 第五章 10 1 1序对 Scheme语言提供的构造函数和选择函数 内部的基本过程 cons模拟构造函数的功能 构造序对 表结构 由序对构造起来的复合数据对象 内部基本过程 car和cdr模拟选择函数的功能 实现对序对的操作 Scheme语言数据抽象 第五章 11 内容 1 数据抽象导引1 1序对1 2有理数包的抽象屏障2 表结构2 1序列与闭包性质2 2表操作2 3表映射3 函数式语言高级抽象综合实例 Scheme语言数据抽象 第五章 12 1 2有理数包的抽象屏障 使用有理数的程序 add rat sub rat make rat numer denom 抽象 抽象 1 2 Scheme语言数据抽象 第五章 13 内容 1 数据抽象导引2 表结构2 1序列与闭包性质2 2表操作2 3表映射3 函数式语言高级抽象综合实例 Scheme语言数据抽象 第五章 14 2 1序列与闭包性质 序对的 盒子和指针表示方式 例如 每个对象表示一个指向盒子的指针左边的方盒放着序对的car右边的方盒放着序对的cdrcons的闭包性质建立元素本身也是序对的序对 表结构 Scheme语言数据抽象 第五章 15 2 1序列与闭包性质 序列 Sequences 表 list 由序对构造出的一种数据结构 表示一批数据对象的有序集合 Scheme语言数据抽象 第五章 16 内容 1 数据抽象导引2 表结构2 1序列与闭包性质2 2表操作2 3表映射3 函数式语言高级抽象综合实例 Scheme语言数据抽象 第五章 17 2 2表操作 例1 Scheme语言数据抽象 第五章 18 2 2表操作 例2 用迭代计算模型改写下面的过程 Scheme语言数据抽象 第五章 19 2 2表操作 例3 实现两个表的合并 Scheme语言数据抽象 第五章 20 内容 1 数据抽象导引2 表结构2 1序列与闭包性质2 2表操作2 3表映射3 函数式语言高级抽象综合实例 Scheme语言数据抽象 第五章 21 2 3表映射 表映射将某种变换应用于一个表的所有元素 得到的结果构成新的表 例如 将一个表中的元素按给定因子缩放 Scheme语言数据抽象 第五章 22 2 3表映射 问题 如何将表的映射这个一般性问题进行抽象 解决方法 将其中的公共模式表述为一个高阶过程map 研究Scheme标准提供的内部map过程 Scheme语言数据抽象 第五章 23 2 3表映射 问题 如何将表的映射这个一般性问题进行抽象 解决方法 将其中的公共模式表述为一个高阶过程map 研究Scheme标准提供的内部map过程 Scheme语言数据抽象 第五章 24 使用map改进scale list Scheme语言数据抽象 第五章 25 内容 1 数据抽象导引2 表结构2 1序列与闭包性质2 2表操作2 3表映射3 函数式语言高级抽象综合实例 实例1 对于一棵树 计算值为奇数的叶子的平方和 实例2 构造所有为偶数的斐波那契数Fib k 的一个表 其中的k小于等于某个给定的整数n 实例1分析 枚举一棵树的树叶 过滤它们 选出其中的奇数 对选出的每一个数求平方 从0开始 用 累积起得到的结果 Scheme语言数据抽象 第五章 28 3函数式语言高级抽象综合实例 实例1和实例2的信号流流水线处理模式 enumerate treeleaves filter odd map square accumulate 0 enumerate integers map fib filter even accumulate cons 枚举从0到n的整数 对每个整数计算相应的斐波那契数 过滤它们选出其中的偶数 从空表开始用cons累积结果 枚举一棵树的树叶 过滤它们选出其中的奇数 对选出的每一个数求平方 从0开始用 累积结果 Scheme语言数据抽象 第五章 29 习题 利用Scheme语言使用下面的标准组件构造由前n 1个斐波那契奇数的平方形成的表 enumeratemapfilteraccumulate