COMPSCI 61A Lecture Notes - Lecture 31: Memoization, Stream Processing, Iterator

• School: Berkeley
• Department: Computer Science
• Course: COMPSCI 61A
• Professor: De Nero John

Document Summary

Sequence operations: map, filter, reduce express seq manipulation using compact expr. Implementation is still constant space: only true, based on lazy implicit nature of range and filter. Is_prime is also a sequence function def is_prime(x): We have to define range and sum ourselves (define (range a b) (if (>= a b) nil (cons a (range( + a 1) b)))) (define (sum s) (reduce + s 0))) (define (prime? x) False (null? (filter (lambda (y) (= 0 (remainder x y)))) (range 2 x)))) (define (sum-primes a b) (sum (filter prime? (range a b)))) Gives same iterators, that doesn"t require mutation that doesn"t. Rest is computed only when needed (car (cons 1 2))-> 1 (cons-stream 1 2)) -> 1. Errors only occur when expressions are evaluated (cons 1 (/ 1 0) -> error (car (cons 1 (/ 1 0)) -> error cons- stream (/1 0) -> (1. Car gets 1, cdr-stream forces computation gets an error.