Edited at

SICP読書女子会#17 2.2.1

More than 3 years have passed since last update.

ついにリストが使える!

SICP/2.2.1.scm at master · cocodrips/SICP

オンラインSICP読書女子会 #17 (2.2 ~ 2.2.1) - connpass

;; list

(define l (list 1 2 3 4))

(display l) ;(1 2 3 4)
(newline)

(display (cdr l)) ;(2 3 4)
(newline)

;; n番目の要素を返す
(display "=====list-ref n番目の要素=====")
(newline)
(define (list-ref items n)
(if (= n 0)
(car items)
(list-ref (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))
(display squares)
(newline)
(display "list-ref 3: ")
(display (list-ref squares 3))
(newline)
;(1 4 9 16 25)
;list-ref 3: 16

;; 長さ
(display "=====length=====")
(newline)
(define (len items)
(if (null? items)
0
(+ 1 (len (cdr items)))))
(display "Length: ")
(display (len squares))
(newline)
;; lengthは定義済みだったので lenを定義

;; リストの合成
(display "=====append リストの合成=====")
(newline)
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2)) ) )

(define l2 (list 1 2 3))
(display l2)
(display " + ")
(display squares)
(display " = ")
(display (append l2 squares))
(newline)
;(1 2 3) + (1 4 9 16 25) = (1 2 3 1 4 9 16 25)


Ex 2.17

listの最後の要素

(display "=====Ex 2.17=====")

(newline)
;; 最後の要素を返すlast-pairを定義

(define (last-pair items)
(if (null? (cdr items))
items
(last-pair (cdr items))))

(display (last-pair squares))
(newline)
;(25)


Ex 2.18

(display "=====Ex 2.18=====")

(newline)
;; リストを逆順に返す

(define (reverse items)
(define (itr src dist)
(if (null? src)
dist
(itr (cdr src) (cons (car src) dist))))
(itr items (list)))

(display (reverse squares))
;(25 16 9 4 1)
(newline)


Ex 2.19

(display "=====Ex 2.19=====")

(newline)
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (cc amount coin-values)
(cond
((= amount 0) 1)
((or (< amount 0) (no-more? coin-values)) 0)
(else
(+
(cc amount (except-first-denomination coin-values))
(cc (- amount (first-denomination coin-values)) coin-values ))
)))
(define (no-more? l) (null? l))
(define (except-first-denomination l) (cdr l))
(define (first-denomination l) (car l))

(display (cc 100 us-coins)) ;292
(newline)


Ex 2.20

(display "=====Ex 2.20=====")

(newline)

(define (same-parity . l)
(define (itr base src dist)
(if (null? src)
dist
(if (= (remainder (car src) 2) base)
(itr base (cdr src) (append dist (list (car src))))
(itr base (cdr src) dist))))
(itr (remainder (car l) 2) l (list)))

(display (same-parity 1 2 3 4 5))
(newline)
;(1 3 5)

(display (same-parity 2 3 4 5 6 10))
(newline)
;(2 4 6 10)


Ex 2.20 別解法 filter

;; Filter実装すればいいっぽい!

(define (filter l f)
(cond
((null? l) (list))
((f (car l)) (cons (car l) (filter (cdr l) f)))
(else (filter (cdr l) f))))

(define (same-parity . l)
(filter l (lambda (x) (= (remainder x 2) (remainder (car l) 2)))))

(display "=====Ex 2.20 filter=====")
(newline)

(display (same-parity 1 2 3 4 5))
(newline)
;(1 3 5)

(display (same-parity 2 3 4 5 6 10))
(newline)
;(2 4 6 10)


別解放 filter && reverseでstack節約

(display "=====Ex 2.20 reverse=====")

(newline)

;; reverse後からすることで、スタックが消費しないようにできる?
(define (filter l f)
(define (filter-itr l f dist)
(cond
((null? l) dist)
((f (car l)) (filter-itr (cdr l) f (cons (car l) dist)))
(else (filter-itr (cdr l) f dist))))
(reverse (filter-itr l f (list))))

(display (same-parity 1 2 3 4 5))
(newline)
;(1 3 5)

(display (same-parity 2 3 4 5 6 10))
(newline)
;(2 4 6 10)