SICP読書女子会#17 2.2.1

  • 0
    いいね
  • 0
    コメント
    この記事は最終更新日から1年以上が経過しています。

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