How to Design Programs -- II.Arbitrarily Data
程序即数据、数据即程序
How to Design Programs
一书聚焦于 GUI 与 批处理 程序
II.Arbitrarily Data
任意大数据
Lists 列表
- cons 本质是一个二元组
- 形式为
'(1 2)- 输出形式为
(1 . 2)使用.进行分隔- list 表示一串二元组嵌套而成的列表
- 形式为
'(1 2 3 4 5)- 本质是
'(cons 1 (cons 2 (cons 3 (cons 4 '()))))最内层的后一个元素(list最后一个元素之后)为 空'()- 输出形式为
(1 2 3 4 5)将空元素省略- 真列表(proper list)的结尾为一个隐式的
'()元素
这也就可以解释,为什么一下用例中 (list? cons-cons) 产生 #f 返回,因为, cons-cons 就不是真列表,而是一个 (cons (list ...) elem) 的二元组
而 (cons? ...) 只需要检测输入是否为二元组,并且检查时直接将 list 展开为 cons 在下列用例中无论如何都返回为 #t
相当于 (cons 1 (list 2 3 4 5)) 相当于 (list 1 2 3 4 5) 将cons内部的list展开
1 | (define test-list |
Computing with Lists 使用列表计算
编写,检索列表中是否存在目标字符串的程序
1 | (define (all-string? . args) |
以上程序,将解析列表中是否存在 “Flatt” 字符串功能分解为三部分
- 列表中是否都为字符串类型
- 安全的字符串相等判定
- 递归判断列表内是否存在 “Flatt” 元素
graph TD
a[all-string?]
b[safe-string=?]
c[contains-flatt?]
a --> b --> c
自指数据定义的设计 Designing With Self-Referential Data Definitions
设计方法
- 如果涉及任意大小的信息,需要一个自指数据定义来表示它。
自指数据定义的有效性必须满足两个条件:
- 必须包含至少两种情况
- 至少有一种情况不得回溯到所定义的数据类型
- 使用数据定义中指向所定义术语的箭头明确标识自指
头部材质:签名、目的陈述和虚拟定义,并没有变化。当制定目的陈述时,重点关注函数 计算了什么 而非 如何实现 尤其是如何处理给定数据的实例
在函数示例中,务必多次处理使用数据定义中自指子句的输入。这是以后制定涵盖整个函数定义测试的最佳方式
从本质上讲,自指数据定义类似于混合数据的数据定义。因此,模板的开发可以按照条目和结构中的方案进行。
- 注意:模板的目的是将数据定义表达为函数布局。
对于函数体,应该从以下几个开始
- 没有递归函数调用的 cond line 称为 base case 基础情况,相应的答案通常都很简单以表述或作为示例
- 处理自指的情况
- 首先,应该明确模板行中每个表达式计算的内容,对于 自然递归 ,我们假设函数已经按照目的陈述中指定操作执行。
- 剩下的就是将各个数值组合起来
对于使用递归进行数值组合的方式,其形式并非那么容易设计,主要是由于进行递归值副本进行传递以及如何传出递归值
根本原因在于:Lisp语言的常量特性,以及值拷贝语义,无法直接进行值更新,需要在不同的递归层间进行返回值的规划
参考以下代码:
1 | ; List-of-strings -> Number |
由于常量语义,副本传递语义,无法管理与更新一个类似于其他命令型语言中的
int size = 0;语法,进行迭代计数
在该段代码中,使用cond对参数(列表)情况进行处理
- (empty? alos) 是否为空,停机情况,从此处将返回值(0:Number)向上传递
- [string? (first alos)]当前列表元素是否是字符串类型
- 向下递归传递 (string? (first alos))
- #t: (+ (List-of-strings (rest alos)) 1) 将递归函数返回值 +1
- #f: [else (+ (List-of-strings (rest alos)) 0)] 将递归函数返回值 +0
所有操作都根源都在与, 如何使用递归替换循环
- 请确保所有函数示例都可以转化为测试,并且检测实例的边界情况