読者です 読者をやめる 読者になる 読者になる

Gauche読書会#2に参加しました

第6章から読み始めました.6章からリストが登場します.
P.56の練習問題を解いてみました.

  • リストの長さを計算するlength
(define (length lst)
  (cond ((null? lst) 0)
        (else (+ 1 (length (cdr lst))))))
  • リストの中から条件を満たす要素だけを抜き出したリストを返すfilter
(define (filter proc lst)
  (cond ((null? lst) '())
        (else (if (proc (car lst))
                (cons (car lst) (filter proc (cdr lst)))
                (filter proc (cdr lst))))))

が,この後の6.6節の末尾再帰を読んでlength, filterが末尾再帰でない.
なので書き直してみる.

(define (length2 lst)
  (define (length-rec lst n)
    (if (null? lst) 
      n
      (length-rec (cdr lst) (+ 1 n))))
  (length-rec lst 0))
(define (filter2 pred lst)
  (define (filter-rec pred lst memo)
    (cond ((null? lst) memo)
          (else (if (pred (car lst))
                  (filter-rec pred (cdr lst) (cons (car lst) memo))
                  (filter-rec pred (cdr lst) memo)))))
  (filter-rec pred lst '()))

これで末尾再帰になったと思ったらfilter2は間違い.

gosh> (filter2 (lambda (x) (if (> x 1) #t #f)) '(1 2 3))
(3 2)

となり,結果がリバースされる.
うむむ...
と,時間中にできたのはこれだけ.第3回目が楽しみです.