Scribd
Upload
172 views2 pages

Scheme Programming Cheat Sheat

1. This document provides a cheat sheet for Scheme concepts including special forms, functions for working with lists and streams. 2. It includes definitions for common list functions like map, filter, accumulate and their stream equivalents as well as functions for working with pairs like cons, car, cdr. 3. Examples are provided for using many of these functions including mapping a function over a list to transform it, accumulating values using a combining function, and inserting an item into a list after a given marker.

Uploaded by

Shams Ansari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
172 views2 pages

Scheme Programming Cheat Sheat

1. This document provides a cheat sheet for Scheme concepts including special forms, functions for working with lists and streams. 2. It includes definitions for common list functions like map, filter, accumulate and their stream equivalents as well as functions for working with pairs like cons, car, cdr. 3. Examples are provided for using many of these functions including mapping a function over a list to transform it, accumulating values using a combining function, and inserting an item into a list after a given marker.

Uploaded by

Shams Ansari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

CS 61A Scheme Midterm 1 Cheat Sheet. 64. (stream-null?

<stream>)
65. (cons-stream <procedure> <procedure>) ;special form where the
<word> is like 'word 2nd procedure is delayed
<sentence> is like '(a b c) 66. (cons-stream <things> <stream>) ;a special form
67. (show-stream <stream>) or (ss <stream> <num>)
1. (member? <word> <sentence>) 68. (interleave <stream> <stream>) ;not a special form, may go into
2. (word <word> <word>) infinite loop
3. (define (<name> <formal parameters>) <body>) [SICP 1.1.4] 69. (append-stream <stream> <stream>)
4. ((equal? <word/sentence> <word/sentence>) <true procedure>) 70. (stream-map <procedure> <thing> <steram>)
5. ( cond ((<condition>) (<true procedure>)) 71. (stream-filter
((<condition>) (<true procedure>)) 72. (stream-append <stream> <stream>) ;the 1st stream has to be
( else (<false procedure>) ) finite
) 73. (delay <procedure>) ;special form, same thing as (lambda ()
6. ( if (<condition>) (<true procedure>) (<false procedure>) ) <exp>)
7. (sentence <word/sentence> <word/sentence> ...) 74. (amb
(se <word/sentence> <word/sentence> ...) 75. (require
8. (butfirst <word/sentence>) 76. (try-again
9. (butlast <word/sentence>)
10. (= <number> <number>) Utility Functions
11. ((empty? <word/sentence>) <true procedure>) 1. close-enough?
12. (count <word/sentence>) (define (close-enough? x y)
13. (last <word/sentence>) (< (abs (- x y)) 0.001))
14. (<= <number> <number>)
15. (and (<condition>) (<condition>) ...) 2. sort [LEC 5]
16. (or (<condition>) (<condition>) ...) (define (sort sent)
17. (not <condition>) (if (empty? sent)
18. (abs <number>) `()
19. (sqrt <number>) (insert (first sent)
20. (sort (bf sent)))))
21. ( expt <number> <number> ) (define (insert num sent)
22. ( lambda (<formal parameters>) <procedure> ) [1.3.2] [lecture 3, (cond ((empty? sent) (se num sent))
special form] ((< num (first sent))
23. (let ( (<variable> (<procedure>) (se num sent))
(<variable> (<procedure>) (...) (else
) (se (first sent)
<body>) (insert num (bf sent))))))
;(let ((<var> <exp>)) <body>) ---> ((lambda (<var>) <body>) <exp>) ;This simplifies to (1/2)N(N-1).
[3.23]
24. (every <procedure> <sentence/word>) [high order function]
25. (number? <anything>) ;returns #t if the argument is a number 3. Open/Close Parenthesis
26. (floor <number>) ;#t if open parentheses equals to close parentheses
27. (ceiling <number>) (define (parenok? w)
28. (prime? <number>) (define (check v open)
29. (keep <predicate> <sentence/word >) [Lecture 7, high order (cond ((empty? v) (= open 0))
function] ((equal? (first v) '"(") (check (bf v) (+ open 1)))
30. (nth <number> <sentence>), (nth 0 '(1 2 3)) -> 1 [lecture 7] ((equal? (first v) '")") (check (bf v) (- open 1)))
31. (define <pair name> (cons <any> <any>)) (else (check (bf v) open))))
32. (car <pair name>) (check w 0))
33. (cdr <pair name>)
34. (list <any> <any>...) [SICP 2.2.1] 4. CONS, CAR, CDR [2.1.4]
35. (let* ( (<variable> (<procedure>) (define (cons x y)
(<variable> (<procedure>) (define (dispatch m)
) (cond ((= m 0) x)
<body>); like every let ((= m 1) y)
36. (append <list> <list> ...) ;return a list of elements (else (error "Argument not 0 or 1 -- CONS" m))))
37. (map <procedure> <list>) dispatch)
38. (length <list>) (define (car z) (z 0))
39. (filter <predicate> <list>) (define (cdr z) (z 1))
40. (pair? <any>)
41. (atom? <anything not a list>) 5.
42. (remainder <number> <number>) LIST <-> SENTENCE
43. (quotient <number> <number>) map <-> every
44. (gcd <number> <number> <number> ...) null? <-> empty?
45. (random <number>) car <-> first
46. (set! <name> <new-value>) cdr <-> butfirst
47. (begin <exp1> <exp2> ... <expk>) filter <-> keep
48. ((eq? <thing1> <thing2>) <expression> ) ;test if it is the same as a
pointer 6.1. MAP, the every for list [2.2.1]
49. (put <op> <type> <item>)
50. (get <op> <type>) [2.43] (define (map proc items)
51. (assoc <word> <list of pairs>) ; (assoc 'a ((b d) (e 3) (a 7))) -> (a (if (null? items)
7), #f is not found nil
52. (random n) ;returns a number between 0 and n (cons (proc (car items))
53. (define-class (<class name> <instantiation variables>) (map proc (cdr items)))))
54. (method (<methodname> <args>) (map abs (list -10 2.5 -11.6 17))
55. (usual <word>) ;call the immediate parent method (10 2.5 11.6 17)
56. (set! <var><var>) ; special form (map (lambda (x) (* x x))
57. (set-car! <pair>) ; not special form (list 1 2 3 4))
58. (set-cdr! <pair>) ; not special form (1 4 9 16)
59. (vector-ref <vector> <index>)
60. (vector-set! <vector> <index> <anything>) 6.2 MAP, add one to every numbers in the list[Lecture 10]
61. (vector-length <vector>) (define (inc x) (+ x 1))
62. (stream-car <stream>)
63. (stream-cdr <stream>) (define (inc-deep-list DL)
(map (lambda (x) (if (list? x) (define (accumulate combiner null-value term a next b)
(inc-deep-list x) (define (iter a result)
(inc x))) (if (> a b)
DL)) result
(inc-deep-list '(0 (1 2 3) 4)) (iter (next a) (combiner (term a) result))))
(1 (2 3 4) 5) (iter a null-value))

6.3 Map, general function ;; sum and product


...
(define (sum term a next b) (accumulate + 0 term a next b))
7. FOR-LOOP, HW 2a
(define (product term a next b) (accumulate * 1 term a next b))
(define (cont-frac n d k) (define (accumulate op null-val sent)
(define (helper i) (if (empty? sent)
(if (> i k) null-val
0 (op (first sent)
(/ (n i) (+ (d i) (accumulate op null-val (bf sent)))))
(helper (+ i 1)))))) > (accumulate + 0 `(2 5 3 4 1))
(helper 1)) 15
>(accumulate word `d `(a b c))
8. INSERT-AFTER a word into a list, error if the item is not found abcd
(define (insert-after item mark lst)
(if (equal? (car lst) mark) 3. > EVERY
(cons (car lst) (cons item (cdr lst))) (define (every f sent)
;(append (list car lst) item) (cdr lst)) (if (empty? sent)
(cons (car lst) (insert-after item mark (cdr lst))) '()
);if (se (f (first sent))
);define (every f (butfirst sent)) )))
(every (lambda (x) (word x ‘s))
9. LIST ‘(tricky hobbits))
(define (list? L)   (trickys hobbitss)
(cond ((null? L) #t)   > (every (lambda (x) (+ x 1)) ‘1234)
((pair? L) (list? (cdr L)))
  (2 3 4 5)
(every (lambda (x) (word x 's)) 'tricky)
(else #f))) (ts rs is cs ks ys)

Special Forms
Note for midterm 1. Define
High Order Functions=every/keep/accumulate 2. If
3. Cond
1.1. KEEP 4. Lambda
> (keep (lambda (x) (= x 1)) ‘(1 2 1 2))
(1 1) Iterative Example
 (define (keep pred sent) (define (exp a b)
 (cond ((empty? sent) ‘()) (if (= b 0)
 ((pred (first sent)) 1
 (se (first sent) (* a (exp a (- b 1)))))
(keep pred (bf sent))))
 (else Recursive Example
 (keep pred (bf sent))))) define (exp a b)
(define (helper count result)
;when parameter is sent (if (= count b)
(define (keep proc sent) result
(if (empty? sent) (helper (+ count 1) (* a result))))
'() (helper 0 1))
(if (proc (first sent))
(se (first sent) (keep proc (bf sent)))
(keep proc (bf sent)))))

(accumulate combiner null-value term a next b)


> (accumulate * 1 (lambda (x) x)
1 (lambda (x) (+ x 1)) 5)
120
> (accumulate se `(foo) (lambda (x) x)
1 (lambda (x) (+ x 1)) 5)
(1 2 3 4 5 foo)

1.2 KEEP
> (keep (lambda (x) (or (even? x) (equal? x 1)))
‘(1 2 3 4))
  (1 2 4)
  > (keep (lambda (x) (member? x ‘(x y z)))
‘syzygy)
  yzyy

2. ACCUMULATE

;; recursive form
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))

;; iterative form

You might also like