S-99 Ninety-Nine Scheme Problems

L-99

EeePC買ってからマック・カフェでちょこちょここれ
L-99: Ninety-Nine Lisp Problems
をSchemeでやってまして、とりあえず第1章・リスト遊び（勝手に章付け）P28まで終わったのでまとめておきます。

  • P01　リストの最後の要素を単一要素のリストで返す関数
 (define (my-last lst)
   (let iter ( (l lst) )
     (if (null? (cdr l)) 
       (list (car l)) 
       (iter (cdr l)))))
  • P02　リストの最後2つの要素をリストで返す関数
 (define (my-but-last ls) 
   (cond
     ( (null? ls) ls) 
     ( (null? (cdr ls)) ls) 
     ( (null? (cddr ls)) ls) 
     (else
       (my-but-last (cdr ls)))))
  • P03　指定の位置の要素を返す関数
 (define (element-at lst index)
   (let iter ( (l lst) (count 1)) 
     (if (>= count index)
       (car l)
       (iter (cdr l) (+ count 1)))))
  • P04　リストの長さを返す関数
 (define (my-length lst) 
   (let iter ( (l lst) (len 0))
     (if (null? l) 
       len
       (iter (cdr l) (+ len 1)))))

ここまでは簡単。ただ再帰するだけ。

  • P05　逆順リスト
 (define (my-reverse lst)
   (let iter ( (l lst) (r '()))
     (if (null? l) 
       r
       (iter (cdr l) (cons (car l) r)))))

リストを潜っていき順に別に用意したリストの先頭に追加していく。

  • P06　リストが回文かどうか判定
 (load "my_reverse.scm") ;P05
 (define (palindrome? lst)
   (if (equal? lst (my-reverse lst))
     #t
     #f))

前のmy-reverseを使って元のリストと等しいか判定する。equal?くらい使ってもいいよね。

  • P07　ネストしたリストを平坦化
 (define (my-flatten lst) 
   (cond ( (null? lst)
          '())
          ( (pair? lst)
           (append (my-flatten (car lst)) (my-flatten (cdr lst))))
          (else (list lst))))

これが書けなくて3日間くらい悩んだ挙句カンニング。appendするとリストが1段階減る。

  • P08　連続した同じ要素を取り除く
 (define (compress lst)
   (let iter ( (l lst) (last '()) (r '()))
              (cond
                ( (null? l)
                 r)
                ( (eq? (car l) last)
                 (iter (cdr l) (car l) r))
                (else
                  (iter (cdr l) (car l) (append r (list (car l))))))))

再帰するときに前回の要素を持っておき、連続しているか判定する。

  • P09　連続した同じ要素をリストにまとめる
 (define (pack ls)
   (let iter ( (l ls) (acc '()) (ret '()))
     (cond
       ( (null? l)
        (if (null? acc)
          ret
          (append ret (list acc))))
       ( (null? acc)
        (iter (cdr l) (append acc (list (car l))) ret))
       ( (eq? (car l) (car acc))
        (iter (cdr l) (append acc (list (car l))) ret))
       (else     
         (iter (cdr l) (list (car l)) (append ret (list acc)))))))

返り値用のリストとは別に一時使用のリストを使う。

  • P10　ランレングス圧縮
 (define (encode ls)
   (let iter ( (l ls) (len 0) (last '()) (ret '()))
     (cond
       ( (null? l)
        (if (= len 0)
          ret
          (append ret (list (list len last)))))
       ( (null? last)
        (iter (cdr l) 1 (car l) ret))
       ( (eq? (car l) last)
        (iter (cdr l) (+ len 1) (car l) ret))
       (else     
         (iter (cdr l) 1 (car l) (append ret (list (list len last))))))))

P09からさらにカウンター用にlet変数追加

とりあえずそろそろ出勤なのでここまで。
>|hoge|<のpre記法の中でも（（hage））←[実際は半角]の脚注が有効なのはLISPerに対する嫌がらせとしか思えない件。