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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
(define test-list
(list
1 (cons 2 3) (list 5 6 7 8) 9))

(define test-cons
(cons
(cons 1 2)
(list 3 4 (cons 5 6) 7 (cons 8 9))))

(define cons-cons
(cons 1
(cons 2
(cons 3
(cons 4 5)))))

(define cons-null
(cons 1
(cons 2
(cons 3 '()))))

(printf "~a\n" test-list)
(printf "~a\n" test-cons)
(printf "~a\n" cons-cons)
(printf "~a\n" cons-null)

(list? cons-cons) ; #f
(cons? cons-cons) ; #t
(list? cons-null) ; #t
(cons? cons-null) ; #t
(list? '(1 2 3 4 5)) ; #t
(cons? '(1 2 3 4 5)) ; #t

(define full-name
(cons "first-name"
(cons "middle-name"
(cons "last-name" '()))))
(display full-name)

(define cons-list
(cons 1 '(2 3 4 5)))
(display cons-list)
(printf "\n")

Computing with Lists 使用列表计算

编写,检索列表中是否存在目标字符串的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (all-string? . args)
(or (empty? args)
(and (string? (first args))
(apply all-string? (rest args)))))
; (andmap string? args))

(define (safe-string=? a b)
(and
(all-string? a b)
(string=? a b)))

(define (contains-flatt? alon)
(and (not (empty? alon))
(or (safe-string=? (first alon) "Flatt")
(contains-flatt? (rest alon)))))

以上程序,将解析列表中是否存在 “Flatt” 字符串功能分解为三部分

  1. 列表中是否都为字符串类型
  2. 安全的字符串相等判定
  3. 递归判断列表内是否存在 “Flatt” 元素


graph TD

    a[all-string?]
    b[safe-string=?]
    c[contains-flatt?]

    a --> b --> c


自指数据定义的设计 Designing With Self-Referential Data Definitions

设计方法

  1. 如果涉及任意大小的信息,需要一个自指数据定义来表示它。

自指数据定义的有效性必须满足两个条件:

  • 必须包含至少两种情况
  • 至少有一种情况不得回溯到所定义的数据类型
    • 使用数据定义中指向所定义术语的箭头明确标识自指
  1. 头部材质:签名、目的陈述和虚拟定义,并没有变化。当制定目的陈述时,重点关注函数 计算了什么 而非 如何实现 尤其是如何处理给定数据的实例

  2. 在函数示例中,务必多次处理使用数据定义中自指子句的输入。这是以后制定涵盖整个函数定义测试的最佳方式

  3. 从本质上讲,自指数据定义类似于混合数据的数据定义。因此,模板的开发可以按照条目和结构中的方案进行。

    • 注意:模板的目的是将数据定义表达为函数布局。
  4. 对于函数体,应该从以下几个开始

    • 没有递归函数调用的 cond line 称为 base case 基础情况,相应的答案通常都很简单以表述或作为示例
    • 处理自指的情况
      • 首先,应该明确模板行中每个表达式计算的内容,对于 自然递归 ,我们假设函数已经按照目的陈述中指定操作执行。
    • 剩下的就是将各个数值组合起来

对于使用递归进行数值组合的方式,其形式并非那么容易设计,主要是由于进行递归值副本进行传递以及如何传出递归值
根本原因在于:Lisp语言的常量特性,以及值拷贝语义,无法直接进行值更新,需要在不同的递归层间进行返回值的规划

参考以下代码:

1
2
3
4
5
6
7
8
9
10
11
; List-of-strings -> Number
; counts how many strings alos contains
(define (List-of-strings alos)
(cond
[(empty? alos) 0]
[(string? (first alos)) (+ (List-of-strings (rest alos)) 1)]
[else (+ (List-of-strings (rest alos)) 0)]))

(define test-list '("a" "b" 1 2 3 #f #t "c" "d" "e"))

(List-of-strings test-list)

由于常量语义,副本传递语义,无法管理与更新一个类似于其他命令型语言中的 int size = 0; 语法,进行迭代计数
在该段代码中,使用 cond 对参数(列表)情况进行处理

  1. (empty? alos) 是否为空,停机情况,从此处将返回值(0:Number)向上传递
  2. [string? (first alos)]当前列表元素是否是字符串类型
  • 向下递归传递 (string? (first alos))
    • #t: (+ (List-of-strings (rest alos)) 1) 将递归函数返回值 +1
    • #f: [else (+ (List-of-strings (rest alos)) 0)] 将递归函数返回值 +0

所有操作都根源都在与, 如何使用递归替换循环

  1. 请确保所有函数示例都可以转化为测试,并且检测实例的边界情况