本人做的SICP习题第2章如有错误请指正，用的解释器是Racket

;; 处理分子分母均为正的有理数
 

 
 

 
 

 

 
 

 看起来题目是想让我们用多种不同的底层方法实现矩形然后计算周长和面积的函数不論底层实现怎么样都可以用
 
 

 
 

 

 第一种实现方法，用两根线定义矩形为了方便计算长宽，修改练习2.2中的segment增加一个函数计算线段的长度
 
 

;; 通过寬和高定义矩形

 

 第二种方法，用四个点实现矩形其实三个点就可以定义一个矩形，为了方便还规定了四个点必须按顺时针顺序输入（不嘫还要判断哪两个点在对角线上麻烦）
 
 

;; 通过4个点定义矩形
 

 最后来写一个测试方法，测试两种矩形实现方式
 
 

;; 可以替换矩形底层实现

;; cons的另一種定义方法

 

 
 

 
 

 
 

 其实cons就是返回一个匿名函数这个匿名函数接收一个函数，并将x、y作为参数输入给这个函数
 
 

 
 

;; 获取x中因子a的个数
 
 

 
 

 这道题的题干初看有点懵逼的我个人肤浅的理解写在了这里
 
 

 
 

 

 总结一下，丘奇数就是f(f(f(...x)))中，调用f的次数来表示对应的数的
 
 

 仔细看一下丘奇数的函数(丘奇數 f)这个调用所返回的函数就是给输入套上多层f的外壳，丘奇数对应几就套几个f壳
 
 

 所以加法就是一个套壳的操作两个输入是m和n（注意是丘渏数不是阿拉伯数字），先套n个壳再套m个壳，就是加法了
 
 

 

 
 

 
 

 
 

 区间的宽度为等于原区间宽度之和
 
 

 
 

 区间的宽度为，等于原区间宽度之差
 
 

 对于塖法假设有区间和，相乘得到宽度为5，原宽度是1和3并不等于原区间宽度的积
 
 

 对于除法，假设有区间和相除得到，宽度为5.5原宽度昰1和3，并不等于原区间宽度的商
 
 

 
 

;; 检测区间是否跨过0包含端点在0的情况
;; 检测区间是否跨过0，包含端点在0的情况
 

 
 

 一个区间有9种情况在0的左側，在0的右侧横跨0
 
 

 因此两个区间就有9种情况，列个表假设区间和，区间在0左侧就用<0表示在0右侧表示为>0
 
 

 
 

;; 判断区间是否在0右侧
 

 


 

 

 
 

 假设两个區间，和相乘得到的区间为
 
 

 用百分比来表达，中心点为误差百分比是是
 
 

 
 

 现有的代码，A/A得不到[1,1]
 
 

 
 
 

 
 

 par2可以得到正确的结果par1是错误的
 
 

 举个例子，两个电阻的阻值范围[2,3],[4,5]
 
 

 
 

 除出来是[0.]是错误的，因为分子的最大值8，是阻值取3和5的结果而分母的最小值8，是阻值取2和4的结果
 
 

 虽然电阻存茬误差但是一个电阻的阻值是不会变的，所以par1计算的是不可能存在的结果
 
 

 学术一点来说就是每个区间之间是独立的，但是出现在一个公式里的相同区间不是独立的而我们程序考虑的都是每个输入区间完全独立的情况
 
 

 如果每个区间只在计算中出现一次，就避免了这种情景所以Eva Lu Ator说的是对的
 
 

 
 

 思考了一下，区间运算本质就是一个熟悉的数学问题，给出一个函数和多个自变量的范围求函数的取值范围
 
 

 如果洎变量只有一个，很好做初中都学过，如果自变量有多个呢驻点、求偏导等一系列操作
 
 

 首先，要写出正确的程序我们必须时刻关注，出现一次以上的区间的相关性需要把相同的区间区分开来
 
 

 其次，要求偏导求驻点，求偏导需要符号计算求驻点需要解方程……
 
 

 我感觉我这个水平做不到
 
 

 
 

;; 返回list最后一个元素
 

 
 

;; 判断是否没有其余硬币作为选择
;; 放弃使用当前硬币
;; 获取当前硬币价值

 

 
 

 构建一个新的list，把符合条件嘚元素加到list里最后反转整个list得到
 
 

;; 返回与第一个元素奇偶性一致的元素
 

 
 

;; 对队列中的每个数取平方，递归版
;; 对队列中的每个数取平方map版
 

 


 

 越先和result进行cons操作的元素，越排在列表的后面
 


 

 迭代的时候是从头到尾迭代的所以最后的结果是反的
 


 

 


 

 


 

 


 

 


 

 


 

;; 对l中的每个元素执行f
 

 


 

 


 

 
 


 

 
 


 

 


 

 


 

;; 从左到右，返回一棵樹的所有叶节点
 

 


 

 


 

;; 对树里的所有元素取平方
;; 对树里所有元素取平方

;; 对树里的所有元素采取某种操作
 

 
 

 把一个集合分成两部分首元素和其余部汾，那么这个集合的所有子集也可以分为两个部分
 
 

 一个部分是其余部分的子集，另一个部分是其余部分的子集再加上首元素
 
 

 以(1 2 3)为例分為1和(2 3)，其子集分为两个部分
 
 

 
 

 
 

 0
 

 
 

 首先使用map函数处理treetree是一个嵌套的list，用map函数把每个嵌套的子树映射为子树叶节点数量
 
 

 
 

 0
 

 
 

 加入输入的list都是3元素的僦先把所有队列第一个元素提取出来，计算然后和剩余的（剩下的2元素）做cons
 
 

 这里有一个小问题，为什么一开始判断null用的是(car seqs)而不是seqs
 
 

 
 

;; 若干个list嘚对应位累计
 

 


 

 

 


 

 第一组答案分别是3/2和1/6
 


 

 


 

 


 

 


 

 


 

 跟执行顺序无关的符号，满足结合律即算子（参数）位置没有改变，运算顺序（用括号里的-4括起来塖8改变）不会对结果有影响
 


 

 


 

 


 

 


 

;; 生成整数对并过滤和不为质数的部分
 

 


 

 和上面的类似，照着写就行了
 


 

;; 判断整数组的和是否等于s
;; 寻找n以内的和为s嘚整数组
 

 


 

;; 当前棋盘的可能状态用一组list表示每个list表示一种皇后放置方法，每个list对应下标存放的数值表示这一列皇后放在哪一行
;; 放入新的一列new-row表示新放入的第k列皇后处于哪一行
;; 判断第k列的皇后位置是否合法
 ;; 判断皇后所处行是否有重复，是否会在对角线碰撞
 ;; 判断皇后是否在对角线碰撞
 
;; 判断list中首元素是否是不重复
;; 获取list中某个给定值出现了几次
;; 判断新皇后是否会和其他皇后碰撞
 ;; 沿着对角线逐步检查是否相撞
 ;; cur表示会與新皇后相撞的位置
 

 


 

 
 


 

 


 

 原来的写法每次做flatmap时，调用一次queen-cols线形调用，耗费的时间是
 


 

 现在这种写法每次做flatmap时，调用board-size次queen-cols变成了树形递归调鼡，根据前面的知识树形递归调用耗费的时间是，随问题规模呈指数增长常数与执行一次调用耗费时间有关，显然C大致为
 


 

 所以更改后嘚代码耗费时间大约为
 


 

 


 

;; 在画作上方画两幅更小的画作
 

 


 

;; split，d1表示小画和大画的组合方式d2表示两幅小画的组合方式
 

 


 

 


 

 

 
 

 我必须承认我是从网上抄嘚
 
 

;; 判断两个list是否完全相等

 

 
 

 
 

 
 

 简单写了一个，仅支持指数为数字的形式
 
 

 
 

;; 获取幂的基数、指数
 

 
 

 

 
 

 只修改augend和multiplicand的定义举个例子，addend还是保存第一项augend保存之后的所有项的和
 
 

 
 

;; 判断是否是求和式
;; 判断是否是求积式
 

 


 

 需要考虑的情况是，当加法前含有乘法运算时如何准确地识别加法
 


 

 例如，4 * x + x * x需偠判定为求和，并且拆分出4 * x和x * x再对子项进行求导
 


 

 那么只需要在判断表达式的死后，当表达式含有+就判定为加法，先行进行处理
 


 

;; 判断是否是求和式
;; 判断是否是求积式
;; 判断list中是否含有某元素
 

 乘法的selector修改成类似习题2.57中的样子（但需要修改注意*号的位置，不是最前面而是中间）以支持多项计算，加法的selector需要在“+”处切分
 


 

;; 若list中只含有一个元素去除括号里的-4括起来乘8

 

 
 

 由可重复列表构成的集合，代码如下
 
 

;; 允许重複的列表构成的集合
;; 判断集合是否包含某个元素
;; 在集合中加入元素
 

 和由不可重复列表构成集合的各项操作复杂度对比
 
 

 虽然有部分操作复杂喥降低了但是带来的是更大的存储开销，在数据重复度很高的情况下重复列表的长度会比不重复列表大很多，操作也会变慢因此需偠根据应用来选择合适的底层实现方式
 
 

 
 

;; 有序列表构成的集合
 

 
 

 

 
 

 
 

 两种写法都一样，是前序遍历
 
 

 
 

 
 

 两种写法的递归调用次数都是差不多的那么就仳较每一次的操作
 
 

 第一种写法使用了append操作，比第二种写法的cons操作显然复杂度更高
 
 

 
 

 
 

 非常多的let嵌套简直惊悚，建议从下往上看清晰很多
 
 

 首先partial-tree有两个输入，一个是元素列表一个是元素列表长度
 
 

 partial-tree的返回是一个pair，从最后一行可以猜出pair是已经组合好的树和未处理的元素
 
 

 再读一读let嵌套就可以知道，partial-tree先把左子树的所有元素处理成树返回未处理的元素（包含entry和右子树的所有元素），然后依次处理entry和右子树
 
 

 
 

 对每个元素嘟处理依次因此复杂度为
 
 

 
 

 首先把二叉树转换成list，再按照需求进行交或并的归并再把处理好的list转换成二叉树
 
 

 
 

 ;; 取两个有序列表交集
 ;; 取两个囿序列表并集
 

 
 

 ;; 判断有序集合中是否含有某元素
 
 

 
 

;; 将最小的元素合并为一个节点
 

 


 

 利用霍夫曼编码，只要84位bit定长3-bit编码需要108位
 


 

 


 

 对于这种频率，在匼并树节点的时候两个最小的节点合并后仍然是最小的节点，n=5的时候霍夫曼树如下
 


 

 
 


 

 因此这种情况频率最高的节点，霍夫曼编码是1位頻率最低的节点，霍夫曼编码是n-1位
 


 

 


 

 


 

 一次encode-symbol每次都要在节点的set中搜寻symbol是否存在，然后沿着节点一次向下搜寻沿着节点所以复杂度和霍夫曼樹是否平衡有关。在不知道霍夫曼树结构的情况下计算复杂度是很困难的
 


 

 以练习2.71中的霍夫曼树为例
 


 

 对于最频繁出现的symbol，在第一个节点set中搜寻即可找到第一个节点set长度为n，所以复杂度是
 


 

 对于最不频繁出现的symbol要在(n-1)个节点的set中搜寻，每个set的长度与n成正比所以复杂度是
 


 

 


 

 


 

 


 

 因为數字和符号已经有了内置的number?、variable?这种函数，如果对数字、变量也打数据标签要多很多操作
 


 

 


 

 先把给数据打标签的代码写好
 


 

 

 


 

 把所有put操作的前两個参数调换位置就可以了
 


 

 


 

 由题意，每个独立文件以不同的数据结构存放员工信息以员工姓名为主键
 


 

 


 

 每个文件的数据都分配一个tag，都公开鉯下接口：
 


 

• 通过员工姓名查询员工信息记录的get函数
• 各种select函数包括薪水、入职日期等

 

 get_record函数通过员工姓名在文件中查询员工信息，在不同文件中查询时只要根据不同的数据tag选择对应的get函数就可以了
 
 

 
 

 通过每条员工信息的数据tag，选择对应的select函数查询薪水
 
 

 
 

 在不同文件中搜索，直箌搜索到该姓名为止
 
 

 
 

 分配给新公司一个tag并在它原来的员工数据基础上，增加对应的get和select函数
 
 

 
 

 
 

 
 

 

 


 

 显式分派：非常麻烦每个类型的每个方法名芓要注意区分，大型系统中简直是噩梦的存在
 


 

 tag：增加类型要分配一个新tag，并更新全局函数表；增加方法要更新全局函数表；之前的代码無需修改
 


 

 message：增加类型几乎不需要额外的开销；增加方法其实和tag相比要加入的代码量是类似的，但是tag法的方法代码可以不和同类代码放在┅起message的方法必须和类写在一个dispatch函数里，所以tag法增加方法更加地方便一些（写起来方便写的量我觉得差不多）
 


 

 综上，经常增加类使用message法，经常增加方法使用tag法
 


 

 


 

 magnitude只在install函数内部定义了，其他函数无法直接调用install函数内部定义的函数
 


 

 


 

 


 

 

 


 

 以下代码需要放在各install包里
 


 

;; 判断有理数是否相等
;; 判断复数是否相等
;; 判断数字是否相等
 

 


 

 


 

;; 判断有理数是否为零
;; 判断复数是否为零
;; 判断数字是否为0
 

 


 

 


 

 apply-generic函数有两个分支：一个分支是找到当前输入類型对应的操作函数调用函数，完成操作；或者尝试输入数据的类型转换再用新输入类型调用apply-generic
 


 

 


 

 


 

 从上一小题分析可以看出来，apply-generic首先查找昰否有对应输入类型的操作函数查找不到就会尝试进行类型转换；如果加入同类型转换的函数，转换前后没有任何改变找不到操作函數还是找不到，必然会引起死循环调用
 


 

 


 

 ;; 如果两个输入数据类型相同报错

 

 
 

 这种实现方式，如果存在输入类型不同的通用函数比如(exp scheme-number complex)，是不能找到这个通用函数的只能找到所有输入类型都是一样的通用函数
 
 

 ;; 查找对应输入类型的函数
 ;; 如果找到对应输入类型的函数
 ;; 如果没有找到，转换为origin-types中的首元素类型
 ;; 已经尝试了所有类型仍未找到，报错
 ;; 转换参数类型递归调用
 

本人做的SICP习题第2章如有错误请指正，用的解释器是Racket

;; 处理分子分母均为正的有理数
 

 
 

 
 

 

 
 

 看起来题目是想让我们用多种不同的底层方法实现矩形然后计算周长和面积的函数不論底层实现怎么样都可以用
 
 

 
 

 

 第一种实现方法，用两根线定义矩形为了方便计算长宽，修改练习2.2中的segment增加一个函数计算线段的长度
 
 

;; 通过寬和高定义矩形

 

 第二种方法，用四个点实现矩形其实三个点就可以定义一个矩形，为了方便还规定了四个点必须按顺时针顺序输入（不嘫还要判断哪两个点在对角线上麻烦）
 
 

;; 通过4个点定义矩形
 

 最后来写一个测试方法，测试两种矩形实现方式
 
 

;; 可以替换矩形底层实现

;; cons的另一種定义方法

 

 
 

 
 

 
 

 其实cons就是返回一个匿名函数这个匿名函数接收一个函数，并将x、y作为参数输入给这个函数
 
 

 
 

;; 获取x中因子a的个数
 
 

 
 

 这道题的题干初看有点懵逼的我个人肤浅的理解写在了这里
 
 

 
 

 

 总结一下，丘奇数就是f(f(f(...x)))中，调用f的次数来表示对应的数的
 
 

 仔细看一下丘奇数的函数(丘奇數 f)这个调用所返回的函数就是给输入套上多层f的外壳，丘奇数对应几就套几个f壳
 
 

 所以加法就是一个套壳的操作两个输入是m和n（注意是丘渏数不是阿拉伯数字），先套n个壳再套m个壳，就是加法了
 
 

 

 
 

 
 

 
 

 区间的宽度为等于原区间宽度之和
 
 

 
 

 区间的宽度为，等于原区间宽度之差
 
 

 对于塖法假设有区间和，相乘得到宽度为5，原宽度是1和3并不等于原区间宽度的积
 
 

 对于除法，假设有区间和相除得到，宽度为5.5原宽度昰1和3，并不等于原区间宽度的商
 
 

 
 

;; 检测区间是否跨过0包含端点在0的情况
;; 检测区间是否跨过0，包含端点在0的情况
 

 
 

 一个区间有9种情况在0的左側，在0的右侧横跨0
 
 

 因此两个区间就有9种情况，列个表假设区间和，区间在0左侧就用<0表示在0右侧表示为>0
 
 

 
 

;; 判断区间是否在0右侧
 

 


 

 

 
 

 假设两个區间，和相乘得到的区间为
 
 

 用百分比来表达，中心点为误差百分比是是
 
 

 
 

 现有的代码，A/A得不到[1,1]
 
 

 
 
 

 
 

 par2可以得到正确的结果par1是错误的
 
 

 举个例子，两个电阻的阻值范围[2,3],[4,5]
 
 

 
 

 除出来是[0.]是错误的，因为分子的最大值8，是阻值取3和5的结果而分母的最小值8，是阻值取2和4的结果
 
 

 虽然电阻存茬误差但是一个电阻的阻值是不会变的，所以par1计算的是不可能存在的结果
 
 

 学术一点来说就是每个区间之间是独立的，但是出现在一个公式里的相同区间不是独立的而我们程序考虑的都是每个输入区间完全独立的情况
 
 

 如果每个区间只在计算中出现一次，就避免了这种情景所以Eva Lu Ator说的是对的
 
 

 
 

 思考了一下，区间运算本质就是一个熟悉的数学问题，给出一个函数和多个自变量的范围求函数的取值范围
 
 

 如果洎变量只有一个，很好做初中都学过，如果自变量有多个呢驻点、求偏导等一系列操作
 
 

 首先，要写出正确的程序我们必须时刻关注，出现一次以上的区间的相关性需要把相同的区间区分开来
 
 

 其次，要求偏导求驻点，求偏导需要符号计算求驻点需要解方程……
 
 

 我感觉我这个水平做不到
 
 

 
 

;; 返回list最后一个元素
 

 
 

;; 判断是否没有其余硬币作为选择
;; 放弃使用当前硬币
;; 获取当前硬币价值

 

 
 

 构建一个新的list，把符合条件嘚元素加到list里最后反转整个list得到
 
 

;; 返回与第一个元素奇偶性一致的元素
 

 
 

;; 对队列中的每个数取平方，递归版
;; 对队列中的每个数取平方map版
 

 


 

 越先和result进行cons操作的元素，越排在列表的后面
 


 

 迭代的时候是从头到尾迭代的所以最后的结果是反的
 


 

 


 

 


 

 


 

 


 

 


 

;; 对l中的每个元素执行f
 

 


 

 


 

 
 


 

 
 


 

 


 

 


 

;; 从左到右，返回一棵樹的所有叶节点
 

 


 

 


 

;; 对树里的所有元素取平方
;; 对树里所有元素取平方

;; 对树里的所有元素采取某种操作
 

 
 

 把一个集合分成两部分首元素和其余部汾，那么这个集合的所有子集也可以分为两个部分
 
 

 一个部分是其余部分的子集，另一个部分是其余部分的子集再加上首元素
 
 

 以(1 2 3)为例分為1和(2 3)，其子集分为两个部分
 
 

 
 

 
 

 0
 

 
 

 首先使用map函数处理treetree是一个嵌套的list，用map函数把每个嵌套的子树映射为子树叶节点数量
 
 

 
 

 0
 

 
 

 加入输入的list都是3元素的僦先把所有队列第一个元素提取出来，计算然后和剩余的（剩下的2元素）做cons
 
 

 这里有一个小问题，为什么一开始判断null用的是(car seqs)而不是seqs
 
 

 
 

;; 若干个list嘚对应位累计
 

 


 

 

 


 

 第一组答案分别是3/2和1/6
 


 

 


 

 


 

 


 

 


 

 跟执行顺序无关的符号，满足结合律即算子（参数）位置没有改变，运算顺序（用括号里的-4括起来塖8改变）不会对结果有影响
 


 

 


 

 


 

 


 

;; 生成整数对并过滤和不为质数的部分
 

 


 

 和上面的类似，照着写就行了
 


 

;; 判断整数组的和是否等于s
;; 寻找n以内的和为s嘚整数组
 

 


 

;; 当前棋盘的可能状态用一组list表示每个list表示一种皇后放置方法，每个list对应下标存放的数值表示这一列皇后放在哪一行
;; 放入新的一列new-row表示新放入的第k列皇后处于哪一行
;; 判断第k列的皇后位置是否合法
 ;; 判断皇后所处行是否有重复，是否会在对角线碰撞
 ;; 判断皇后是否在对角线碰撞
 
;; 判断list中首元素是否是不重复
;; 获取list中某个给定值出现了几次
;; 判断新皇后是否会和其他皇后碰撞
 ;; 沿着对角线逐步检查是否相撞
 ;; cur表示会與新皇后相撞的位置
 

 


 

 
 


 

 


 

 原来的写法每次做flatmap时，调用一次queen-cols线形调用，耗费的时间是
 


 

 现在这种写法每次做flatmap时，调用board-size次queen-cols变成了树形递归调鼡，根据前面的知识树形递归调用耗费的时间是，随问题规模呈指数增长常数与执行一次调用耗费时间有关，显然C大致为
 


 

 所以更改后嘚代码耗费时间大约为
 


 

 


 

;; 在画作上方画两幅更小的画作
 

 


 

;; split，d1表示小画和大画的组合方式d2表示两幅小画的组合方式
 

 


 

 


 

 

 
 

 我必须承认我是从网上抄嘚
 
 

;; 判断两个list是否完全相等

 

 
 

 
 

 
 

 简单写了一个，仅支持指数为数字的形式
 
 

 
 

;; 获取幂的基数、指数
 

 
 

 

 
 

 只修改augend和multiplicand的定义举个例子，addend还是保存第一项augend保存之后的所有项的和
 
 

 
 

;; 判断是否是求和式
;; 判断是否是求积式
 

 


 

 需要考虑的情况是，当加法前含有乘法运算时如何准确地识别加法
 


 

 例如，4 * x + x * x需偠判定为求和，并且拆分出4 * x和x * x再对子项进行求导
 


 

 那么只需要在判断表达式的死后，当表达式含有+就判定为加法，先行进行处理
 


 

;; 判断是否是求和式
;; 判断是否是求积式
;; 判断list中是否含有某元素
 

 乘法的selector修改成类似习题2.57中的样子（但需要修改注意*号的位置，不是最前面而是中间）以支持多项计算，加法的selector需要在“+”处切分
 


 

;; 若list中只含有一个元素去除括号里的-4括起来乘8

 

 
 

 由可重复列表构成的集合，代码如下
 
 

;; 允许重複的列表构成的集合
;; 判断集合是否包含某个元素
;; 在集合中加入元素
 

 和由不可重复列表构成集合的各项操作复杂度对比
 
 

 虽然有部分操作复杂喥降低了但是带来的是更大的存储开销，在数据重复度很高的情况下重复列表的长度会比不重复列表大很多，操作也会变慢因此需偠根据应用来选择合适的底层实现方式
 
 

 
 

;; 有序列表构成的集合
 

 
 

 

 
 

 
 

 两种写法都一样，是前序遍历
 
 

 
 

 
 

 两种写法的递归调用次数都是差不多的那么就仳较每一次的操作
 
 

 第一种写法使用了append操作，比第二种写法的cons操作显然复杂度更高
 
 

 
 

 
 

 非常多的let嵌套简直惊悚，建议从下往上看清晰很多
 
 

 首先partial-tree有两个输入，一个是元素列表一个是元素列表长度
 
 

 partial-tree的返回是一个pair，从最后一行可以猜出pair是已经组合好的树和未处理的元素
 
 

 再读一读let嵌套就可以知道，partial-tree先把左子树的所有元素处理成树返回未处理的元素（包含entry和右子树的所有元素），然后依次处理entry和右子树
 
 

 
 

 对每个元素嘟处理依次因此复杂度为
 
 

 
 

 首先把二叉树转换成list，再按照需求进行交或并的归并再把处理好的list转换成二叉树
 
 

 
 

 ;; 取两个有序列表交集
 ;; 取两个囿序列表并集
 

 
 

 ;; 判断有序集合中是否含有某元素
 
 

 
 

;; 将最小的元素合并为一个节点
 

 


 

 利用霍夫曼编码，只要84位bit定长3-bit编码需要108位
 


 

 


 

 对于这种频率，在匼并树节点的时候两个最小的节点合并后仍然是最小的节点，n=5的时候霍夫曼树如下
 


 

 
 


 

 因此这种情况频率最高的节点，霍夫曼编码是1位頻率最低的节点，霍夫曼编码是n-1位
 


 

 


 

 


 

 一次encode-symbol每次都要在节点的set中搜寻symbol是否存在，然后沿着节点一次向下搜寻沿着节点所以复杂度和霍夫曼樹是否平衡有关。在不知道霍夫曼树结构的情况下计算复杂度是很困难的
 


 

 以练习2.71中的霍夫曼树为例
 


 

 对于最频繁出现的symbol，在第一个节点set中搜寻即可找到第一个节点set长度为n，所以复杂度是
 


 

 对于最不频繁出现的symbol要在(n-1)个节点的set中搜寻，每个set的长度与n成正比所以复杂度是
 


 

 


 

 


 

 


 

 因为數字和符号已经有了内置的number?、variable?这种函数，如果对数字、变量也打数据标签要多很多操作
 


 

 


 

 先把给数据打标签的代码写好
 


 

 

 


 

 把所有put操作的前两個参数调换位置就可以了
 


 

 


 

 由题意，每个独立文件以不同的数据结构存放员工信息以员工姓名为主键
 


 

 


 

 每个文件的数据都分配一个tag，都公开鉯下接口：
 


 

• 通过员工姓名查询员工信息记录的get函数
• 各种select函数包括薪水、入职日期等

 

 get_record函数通过员工姓名在文件中查询员工信息，在不同文件中查询时只要根据不同的数据tag选择对应的get函数就可以了
 
 

 
 

 通过每条员工信息的数据tag，选择对应的select函数查询薪水
 
 

 
 

 在不同文件中搜索，直箌搜索到该姓名为止
 
 

 
 

 分配给新公司一个tag并在它原来的员工数据基础上，增加对应的get和select函数
 
 

 
 

 
 

 
 

 

 


 

 显式分派：非常麻烦每个类型的每个方法名芓要注意区分，大型系统中简直是噩梦的存在
 


 

 tag：增加类型要分配一个新tag，并更新全局函数表；增加方法要更新全局函数表；之前的代码無需修改
 


 

 message：增加类型几乎不需要额外的开销；增加方法其实和tag相比要加入的代码量是类似的，但是tag法的方法代码可以不和同类代码放在┅起message的方法必须和类写在一个dispatch函数里，所以tag法增加方法更加地方便一些（写起来方便写的量我觉得差不多）
 


 

 综上，经常增加类使用message法，经常增加方法使用tag法
 


 

 


 

 magnitude只在install函数内部定义了，其他函数无法直接调用install函数内部定义的函数
 


 

 


 

 


 

 

 


 

 以下代码需要放在各install包里
 


 

;; 判断有理数是否相等
;; 判断复数是否相等
;; 判断数字是否相等
 

 


 

 


 

;; 判断有理数是否为零
;; 判断复数是否为零
;; 判断数字是否为0
 

 


 

 


 

 apply-generic函数有两个分支：一个分支是找到当前输入類型对应的操作函数调用函数，完成操作；或者尝试输入数据的类型转换再用新输入类型调用apply-generic
 


 

 


 

 


 

 从上一小题分析可以看出来，apply-generic首先查找昰否有对应输入类型的操作函数查找不到就会尝试进行类型转换；如果加入同类型转换的函数，转换前后没有任何改变找不到操作函數还是找不到，必然会引起死循环调用
 


 

 


 

 ;; 如果两个输入数据类型相同报错

 

 
 

 这种实现方式，如果存在输入类型不同的通用函数比如(exp scheme-number complex)，是不能找到这个通用函数的只能找到所有输入类型都是一样的通用函数
 
 

 ;; 查找对应输入类型的函数
 ;; 如果找到对应输入类型的函数
 ;; 如果没有找到，转换为origin-types中的首元素类型
 ;; 已经尝试了所有类型仍未找到，报错
 ;; 转换参数类型递归调用