> <\body> <\hide-preamble> >>> <\slideshow> <\slide> \; \; \; \; \<#57FA\>\<#7840\>SICP 10>|>>|\<#6D6A\>\<#718A\>\<#732B\>\<#513F\>>>>|>>|\<#6570\>\<#5F0F\>\<#7F16\>\<#7A0B\>\<#4E09\>\<#677F\>\<#65A7\>>> <\slide> \<#57FA\>\<#7840\>SICP\<#FF1A\>\<#7B2C\>10\<#8BFE\>> <\wide-tabular> || <\large> \<#636E\>\<#62BD\>\<#8C61\>\<#5BFC\>\<#5F15\>> |<\cell> <\large> n >| \<#5B9E\>\<#4F8B\>\<#FF1A\>\<#6709\>\<#7406\>\<#6570\>\<#7684\>\<#7B97\>\<#672F\>\<#8FD0\>\<#7B97\> |<\cell> Example: Arithmetic Operations for Rational Numbers >| \<#62BD\>\<#8C61\>\<#5C42\>\<#7EA7\> |<\cell> Abstraction Barriers >| \<#6570\>\<#636E\>\<#610F\>\<#5473\>\<#7740\>\<#4EC0\>\<#4E48\> |<\cell> What Is Meant by Data? >| \<#6B21\>\<#6027\>\<#6570\>\<#636E\>\<#548C\>\<#5305\>\<#6027\>\<#8D28\>>>> |<\cell> > >| \<#5E8F\>\<#5217\>\<#7684\>\<#8868\>\<#793A\> |<\cell> Representing Sequences >| \<#5C42\>\<#6B21\>\<#6027\>\<#7ED3\>\<#6784\> |<\cell> Hierarchical Structures >| \<#5E8F\>\<#5217\>\<#4F5C\>\<#4E3A\>\<#4E00\>\<#79CD\>\<#7EA6\>\<#5B9A\>\<#7684\>\<#63A5\>\<#53E3\> |<\cell> Sequences as Conventional Interfaces >>> \; \<#7528\>\<#51FD\>\<#6570\>\<#5F0F\>\<#7F16\>\<#7A0B\>\<#4E09\>\<#677F\>\<#65A7\>\<#FF08\>\<#6620\>\<#5C04\>/\<#8FC7\>\<#6EE4\>/\<#6298\>\<#53E0\>\<#FF09\>\<#548C\>\<#884D\>\<#751F\>\<#7B97\>\<#5B50\>\<#63CF\>\<#8FF0\>\<#6570\>\<#636E\>\<#5904\>\<#7406\>\<#903B\>\<#8F91\>\<#3002\>> \; <\slide> \<#4E49\>\<#6570\>\<#636E\>\<#FF1A\>list> \<#901A\>\<#8FC7\>\<#5B9A\>\<#4E49\>\<#4E00\>\<#7EC4\>\<#8F91\>\<#81EA\>\<#6D3D\>>\<#7684\>\<#9009\>\<#62E9\>\<#51FD\>\<#6570\>\<#548C\>\<#6784\>\<#9020\>\<#51FD\>\<#6570\>\<#FF0C\>\<#5B9A\>\<#4E49\>\<#6570\>\<#636E\>\<#3002\> <\with|par-columns|2> \<#6784\>\<#9020\>\<#5668\> <\session|s7|default> <\unfolded-io> \\ <|unfolded-io> (list 1 2 3 4) <|unfolded-io> (1 2 3 4) <\folded-io> \\ <|folded-io> (cons 5 (list 1 2 3 4)) <|folded-io> (5 1 2 3 4) <\folded-io> \\ <|folded-io> () <|folded-io> () <\input> \\ <|input> \; \<#9009\>\<#62E9\>\<#5668\> <\session|s7|default> <\folded-io> \\ <|folded-io> (car (list 1 2 3 4)) <|folded-io> 1 <\folded-io> \\ <|folded-io> (cdr (list 1 2 3 4)) <|folded-io> (2 3 4) <\folded-io> \\ <|folded-io> (cadr (list 1 2 3 4)) <|folded-io> 2 <\folded-io> \\ <|folded-io> (list-ref (list 1 2 3 4) 3) <|folded-io> 4 <\input> \\ <|input> \; \<#6027\>\<#8D28\> <\session|s7|default> <\folded-io> \\ <|folded-io> (list? (list 1)) <|folded-io> #t <\folded-io> \\ <|folded-io> (list? 1) <|folded-io> #f <\folded-io> \\ <|folded-io> (eq? () ()) <|folded-io> #t <\folded-io> \\ <|folded-io> (eq? () (list 1)) <|folded-io> #f <\folded-io> \\ <|folded-io> (null? ()) <|folded-io> #t <\input> \\ <|input> (length (list 1 2 3 4)) <\slide> \<#677F\>\<#65A7\>\<#4E4B\>\<#6620\>\<#5C04\>\<#FF1A\>map> \<#662F\>S7 Scheme\<#7684\>\<#5185\>\<#7F6E\>\<#51FD\>\<#6570\> <\session|s7|default> <\folded-io> \\ <|folded-io> (define (square x) (* x x)) <|folded-io> square <\folded-io> \\ <|folded-io> (map square (list 1 2 3 4 5)) <|folded-io> (1 4 9 16 25) <\folded-io> \\ <|folded-io> (map (lambda (x) (* x x)) (list 1 2 3 4 5)) <|folded-io> (1 4 9 16 25) <\folded-io> \\ <|folded-io> (map (lambda (x) (+ x 1)) (list 1 2 3 4 5)) <|folded-io> (2 3 4 5 6) <\folded-io> \\ <|folded-io> (map (lambda (x) (append x "@liii.pro")) (list "da" "nian")) <|folded-io> ("da@liii.pro" "nian@liii.pro") <\folded-io> \\ <|folded-io> (map odd? (list 1 2 3 4 5)) <|folded-io> (#t #f #t #f #t) <\input> \\ <|input> \; <\slide> \<#677F\>\<#65A7\>\<#4E4B\>\<#8FC7\>\<#6EE4\>\<#FF1A\>filter> \<#4E2D\>\<#5B9A\>\<#4E49\>\<#4E86\>\<#FF0C\>\<#6211\>\<#4EEC\>\<#9700\>\<#8981\>\<#81EA\>\<#5DF1\>\<#5B9E\>\<#73B0\> <\with|par-columns|2> \<#5B9E\>\<#73B0\> <\session|s7|default> <\unfolded-io> \\ <|unfolded-io> (define (filter pred? seq) \ \ (cond \ \ \ ((null? seq) ()) \ \ \ ((pred? (car seq)) \ \ \ \ (cons (car seq) \ \ \ \ \ \ \ \ \ \ (filter pred? (cdr seq)))) \ \ \ (else (filter pred? (cdr seq))))) <|unfolded-io> filter \<#5E94\>\<#7528\> <\session|s7|default> <\folded-io> \\ <|folded-io> (filter odd? (list 1 2 3 4 5)) <|folded-io> (1 3 5) <\folded-io> \\ <|folded-io> (filter even? (list 1 2 3 4 5)) <|folded-io> (2 4) <\folded-io> \\ <|folded-io> (filter (lambda (x) (\ x 3)) '(1 3 5)) <|folded-io> (5) <\folded-io> \\ <|folded-io> (filter (lambda (x) (= x 3)) `(1 3 5)) <|folded-io> (3) <\folded-io> \\ <|folded-io> (filter (lambda (x) (\ x 20)) \ (map (lambda (x) (* x x)) \ \ (list 1 2 3 4 5 6))) <|folded-io> (25 36) <\input> \\ <|input> \; <\slide> \<#677F\>\<#65A7\>\<#4E4B\>\<#6298\>\<#53E0\>\<#FF1A\>fold\<#548C\>fold-right> \<#4E2D\>\<#5B9A\>\<#4E49\>\<#4E86\>\<#FF0C\>\<#6211\>\<#4EEC\>\<#9700\>\<#8981\>\<#81EA\>\<#5DF1\>\<#5B9E\>\<#73B0\> <\with|par-columns|2> \<#5B9E\>\<#73B0\> <\session|s7|default> <\folded-io> \\ <|folded-io> (define (fold op initial seq) \ (if (null? seq) \ \ initial \ \ (fold op \ \ \ \ \ \ \ \ (op (car seq) initial) \ \ \ \ \ \ \ \ (cdr seq)))) <|folded-io> fold <\folded-io> \\ <|folded-io> (define (fold-right op initial seq) \ (if (null? seq) \ \ initial \ \ (op (car seq) \ \ \ \ \ \ (fold-right op \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ initial \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (cdr seq))))) <|folded-io> fold-right \<#5E94\>\<#7528\> <\session|s7|default> <\unfolded-io> \\ <|unfolded-io> (fold + 0 (list 1 2 3 4)) <|unfolded-io> 10 <\unfolded-io> \\ <|unfolded-io> (fold-right + 0 (list 1 2 3 4)) <|unfolded-io> 10 <\unfolded-io> \\ <|unfolded-io> (fold cons () (list 1 2 3 4)) <|unfolded-io> (4 3 2 1) <\unfolded-io> \\ <|unfolded-io> (fold-right cons () (list 1 2 3 4)) <|unfolded-io> (1 2 3 4) <\input> \\ <|input> \; <\slide> \<#89E3\>\<#5DE6\>\<#6298\>\<#53E0\>fold> \<#901A\>\<#8FC7\>\<#53EF\>\<#89C6\>\<#5316\>\<#7406\>\<#89E3\> <\with|par-columns|4> <\scm-code> ; Step 0 (fold cons\ \ \ () \ |1||2||3|\>>>) ; Step 1 (fold cons\ \ \ |1|\> \; \ |2||3|\>>) ; Step 2 (fold cons \ |2||1|\>> \; \ \ |3|\>) \; ; Step 3 (fold cons |3||2||1|\>>> ()) <\slide> \<#89E3\>\<#53F3\>\<#6298\>\<#53E0\>fold-right\<#6B65\>\<#9AA4\>0-1> \<#901A\>\<#8FC7\>\<#53EF\>\<#89C6\>\<#5316\>\<#7406\>\<#89E3\> <\with|par-columns|2> <\scm-code> ; Step 0 (fold-right cons () |1||2||3|\>>>) ; Step 1 (cons 1 \ (fold-right cons () |2||3|\>>))) \; \; <\slide> \<#89E3\>\<#53F3\>\<#6298\>\<#53E0\>fold-right\<#6B65\>\<#9AA4\>2-3> \<#901A\>\<#8FC7\>\<#53EF\>\<#89C6\>\<#5316\>\<#7406\>\<#89E3\> <\with|par-columns|2> <\scm-code> ; Step 2 (cons 1 \ (cons 2 \ \ (fold-right cons () |3|\>))) \; \; \; \; \; \; ; Step 3 (cons 1 (cons 2 (cons 3 ())))) |1||2||3|\>>> \; <\slide> \<#751F\>\<#7B97\>\<#5B50\>\<#FF1A\>flatmap> <\session|s7|default> <\unfolded-io> \\ <|unfolded-io> (define (flatmap f seq) \ \ (fold-right append () (map f seq))) <|unfolded-io> flatmap <\unfolded-io> \\ <|unfolded-io> (flatmap (lambda (x) (list x x)) (list 1 2 3 4)) <|unfolded-io> (1 1 2 2 3 3 4 4) <\unfolded-io> \\ <|unfolded-io> (map (lambda (x) (list x x)) (list 1 2 3 4)) <|unfolded-io> ((1 1) (2 2) (3 3) (4 4)) <\input> \\ <|input> \; <\equation*> map:|||>>>>|>>|>>>>>|>|>>>>>|>|>>>>>|>|>>>>>>>>> <\equation*> flatmap:|||>>>>|>|||||||>>>> <\slide> \<#751F\>\<#7B97\>\<#5B50\>\<#FF1A\>flatmap\<#7684\>\<#5E94\>\<#7528\>> <\session|s7|default> <\folded-io> \\ <|folded-io> (define (remove item sequence) \ \ (filter (lambda (x) (not (= x item))) \ \ \ \ \ \ \ \ \ \ sequence)) <|folded-io> remove <\folded-io> \\ <|folded-io> (define (permutations s) \ \ (if (null? s) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ; empty set? \ \ \ \ \ \ (list ()) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ; sequence containing empty set \ \ \ \ \ \ (flatmap (lambda (x) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (map (lambda (p) (cons x p)) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (permutations (remove x s)))) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ s))) <|folded-io> permutations <\unfolded-io> \\ <|unfolded-io> (permutations (list 1 2 3)) <|unfolded-io> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)) <\input> \\ <|input> \; <\slide> \<#7ED3\>> <\itemize> \<#5B9A\>\<#4E49\>\<#6570\>\<#636E\>: list \<#4E09\>\<#677F\>\<#65A7\>\<#4E4B\>\<#6620\>\<#5C04\>map \<#4E09\>\<#677F\>\<#65A7\>\<#4E4B\>\<#8FC7\>\<#6EE4\>filter \<#4E09\>\<#677F\>\<#65A7\>\<#4E4B\>\<#6298\>\<#53E0\>fold/fold-right \<#884D\>\<#751F\>\<#7B97\>\<#5B50\>\<#FF1A\>\<#53C2\>\<#8003\> <\itemize> flatmap find any (\) every (\) count reduce/reduce-right <\initial> <\collection>