1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

SICP読書女子会#17 2.2.1

Last updated at Posted at 2016-07-27

ついにリストが使える!
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)
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?