Introduction to Data Structure
What is Meant by Data?
- The definition of Data
- 使用procedure實(shí)現(xiàn)cons,car以及cdr.
- 使用條件語句實(shí)現(xiàn)這三個內(nèi)置函數(shù).
- 其實(shí)可以讓cons支持有限個參數(shù)(>2個),只需要在條件語句上多加幾個情況.
- Message Passing
- definition: What is message passing?
- Exercises 2.4
- Analyse the requirements
-
(car (cons x y))
- (cons x y) 是作為參數(shù)傳入car的，實(shí)際上會生成一個procedure m
- (car z) 返回的也是一個procedure，這個返回的procedure的作用就是返回第一個參數(shù)港庄。
- 所以這整個函數(shù)的作用就是car设联，返回第一個參數(shù)。
-
寫一個cdr的procedure褥影。
- Section 1.1.5
- substitution model
- (f 5), this f is the procedure (sum-of-squares )
- When we are trying to evaluate f ,this f is replaced by procedure (sum-of-squares)
- Why do we need to use the substitution model?
- Because we need to verify whether cdr works
- substitution model
- The idea is to implement a procedure take the second parameter out as the return.
- We need the cdr procedure to do something as follows
(cdr (cons x y)) returns y
* So the arguments of cdr should be a procedure , and the return value should also be a concrete object rather than a procedure.
>(define (cdr z) (z (lambda (x y) y))
- Section 1.1.5
- How to implement the cons as a procedure?
- (cons a b) -- (lambda (m) (m x y))
- what is the return value of ‘cons'?
- The return value is a kind of data structure. 'Data structure Object’
- The return value can be manipulated by 'car' and 'cdr',
- So the return value is a procedure.
- What are the arguments of the procedure?
"""
(define k (cons 4 5))
(cdr k)
(k (lambda (x y) y)
(cons (4 5)) (lambda (x y) y)
(lambda (m) (m 4 5)) (lambda ( x y) y)
(lambda (x y) y) (4 5)
5
"""
- What are the arguments of the procedure?
- So the return value is a procedure.
Conclution
- We can implement cons car cdr by ourself
- The cons returns a procedure which is the highest abstraction structure.
- take procedure as arguments
- returns object is also a procedure
- We can make up our mind by implement the structure step by step.
