youtube self reference 公开课
通过我们之前的笔记我们知道
atomic, interval, Enumeration, Itemization 是一种基础数据类型表达一抽象概念(一对一的关系)
比如Cat is Natural. CountDown is Natural[0, 10],...
compund 是用两种以上数据组合起来表示一抽象概念
比如
(define-struct cow (x dx))
;; Cow is (make-cow Naturla[0, WIDTH], Integer)
假设我们要表示一群牛， 那该怎么写尼。。。
这章便引入了arbitrary size(list)这个概念, 关于list 的操作方法叫做self reference。
从这章开始，开始引入了recursion(递归)的概念
这里我们用ListOfNumber 作为例子
(require spd/tags)
(@htdd ListOfNumber)
;; ListOfNumber is one of:
;; - empty
;; - (cons Number ListOfNumber)
;; interp. arbitrarily long list of arbitrary numbers
(define LON0 empty)
(define LON1 (cons 1 empty))
(define LON2 (cons 2 LON1))
(define LON3 (cons 3 LON2))
(@dd-template-rules one-of ;2 cases
atomic-distinct ;empty
compound ;(cons Number ListOfNumber)
self-ref) ;(rest lo) is ListOfNumber
#;
; template for ListOfNumber
(define (fn-for-lon lon)
(cond [(empty? lon) (...)]
[else
(... (first lon)
(fn-for-lon (rest lon)))]))
;; ListOfNumber is one of:
;; - empty
;; - (cons Number ListOfNumber)
这两句看起来很奇怪。。。 相当的奇怪。。。
其实是在讲这么一个事情， 一堆数字只分两种情况，
一是empty的，
要不就是有数字的，
而任何有(n + 1)个数字的集合都是可以由一个n个数字的集合加一个数字组成(cons Number ListOfNumber)
(define LON0 empty)
(define LON1 (cons 1 empty))
(define LON2 (cons 2 LON1))
(define LON3 (cons 3 LON2))
。。。
相当于我们用递归的想法去定义了一堆数字
接着我们用一题例题，去看一下template是怎么recursion的
(@htdf sum-of-nums)
(@signature ListOfNumber -> Number)
;; output the sum of the numbers in the list
(check-expect (sum-of-nums empty) 0)
(check-expect (sum-of-nums (cons 3 (cons 2 (cons 1 empty)))) 6)
;(define (sum-of-nums lon) 0) ;stub
(@template ListOfNumber)
(define (sum-of-nums lon)
(cond [(empty? lon) 0]
[else
(+ (first lon)
(sum-of-nums (rest lon)))]))
(sum-of-nums (cons 3 (cons 2 (cons 1 empty))))的运算过程
(sum-of-nums (cons 3 (cons 2 (cons 1 empty))))
=(+ 3
(sum-of-nums (cons 2 (cons 1 empty))))
=(+ 3
(+ 2
(sum-of-nums (cons 1 empty))))
= (+ 3
(+ 2
(+ 1 (sum-of-nums empty))))
= (+ 3
(+ 2
(+ 1 0)))
=6
[(empty? lon) (...)]是整个recursion 能停下来的关键， 又叫base case，
这里当list 是empty 的时候 产生0