函数式程序设计语言.ppt
,2023年10月6日星期五,程序设计语言范型Programming Languages Paradigms,教师：张荣华计算机科学与技术学院华北电力大学,函数式程序设计语言,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:tree leaves,filter:odd?,map:square,accumulate:+，0,enumerate:integers,map:fib,filter:even?,accumulate:cons，(),枚举从0到n的整数,对每个整数计算相应的斐波那契数,过滤它们选出其中的偶数,从空表开始用cons累积结果,枚举一棵树的树叶,过滤它们选出其中的奇数,对选出的每一个数求平方,从0开始用+累积结果,Scheme语言数据抽象,第五章-29,习题,利用Scheme语言使用下面的标准组件构造由前n+1个斐波那契奇数的平方形成的表。enumeratemapfilteraccumulate,
