ITコンサルの日常

ITコンサル会社に勤務する普通のITエンジニアの日常です。

「ANSI Common Lisp」3章練習問題

1. 箱表記で以下のリストを示せ。

(d)はちょっと自信なし。


2. もとのリストでの要素の並びを保持するように動作するunionの変形版を書け。

(defun new-union (x y)
  (if (null y)
    x
    (if (member (car y) x)
      (new-union x (cdr y))
      (new-union (append x (list (car y))) (cdr y)))))

(new-union '(a b c) '(b a d))

xにyを再帰で追加していくイメージ。yのcarが既にxに含まれていれば追加しない。
結果はこう。

* 
NEW-UNION
* 
(A B C D)
*

3. 1つのリストを引数として、おのおのの要素について同じもの(eqlで比較)が出現する回数を示すリストを返す関数を定義せよ。ただし、結果は回数が多い順に並べ替えて返すものとする。

(defun occurrences (lst)
  (if (null lst)
    nil
    (let ((result-list (occurrences (cdr lst))))
       (let ((if-include (member (car lst) result-list :key #'car)))
         (if if-include
           (sort (append (remove (car lst) result-list :key #'car) (list (cons (
car lst) (+ (cdr (car if-include)) 1)))) #'> :key #'cdr)
           (sort (append result-list (list (cons (car lst) 1))) #'> :key #'cdr))
))))

(occurrences '(a b a d a c d c a))

ぐちゃぐちゃや。。
でも、結果は出来てるっぽい。

* 
OCCURRENCES
* 
((A . 4) (C . 2) (D . 2) (B . 1))
* 

4. なぜ(member '(a) '((a) (b)))はnilを返すのか?

(eql 最初の(a) 後の(a)) => nil
だからじゃないですかね。

* (member '(a) '((a) (b)) :test #'eql)

NIL
* (member '(a) '((a) (b)) :test #'equal)

((A) (B))
* 

っていうことですね。

5. 関数pos+は1つのリストを引数として、おのおのの要素にその位置を示す数を加えて返す。この関数を、(a)再帰を用いる、(b)反復を用いる、(c)mapcarを用いる、の3通りで定義せよ。

; (a) 再帰版
(defun pos+-recursive (lst)
  (if (null lst)
    nil
    (let ((last-elem (car (last lst))))
      (append (pos+-recursive (subseq lst 0 (- (length lst) 1))) (list (- (+ las
t-elem (length lst)) 1))))))

; (b) 反復版
(defun pos+-loop (lst)
  (let ((result ()))
    (do ((i 0 (+ i 1)))
        ((> i (- (length lst) 1)) result)
       (setf result (append result (list (+ (nth i lst) i)))))))

; (c) mapcar版
(defun pos+-mapcar (lst)
  (mapcar #'+ lst (make-zero-origin-sequence (length lst))))

(defun make-zero-origin-sequence (n)
  (if (< n 0)
    nil
    (append (make-zero-origin-sequence (- n 1)) (list n))))

; mainルーチン(テストドライバ)
(pos+-recursive '(7 5 1 4))
(pos+-loop '(7 5 1 4))
(pos+-mapcar '(7 5 1 4))

僕的な難易度は高い順に(a) > (b) > (c)でした。
再帰版は、car/cdrを使わずに、lastをcar、それ以外をcdrみたいな感じで作ってみました。

* 
POS+-RECURSIVE
* 
POS+-LOOP
* 
POS+-MAPCAR
* 
MAKE-ZERO-ORIGIN-SEQUENCE
* 
(7 6 3 7)
* 
(7 6 3 7)
* 
(7 6 3 7)
* 

6. 長年にわたる審議の末、ある政府委員会が次のように決定した。リストは第1要素を示すためにcdrを用い、その残りを示すためにcarを用いなければならない。この方針にしたがって以下の関数を定義せよ。

誤植か? と思わせるような内容ですが、さっぱり意味が分かりません。。


本には練習問題の回答は載っていないのですが、
http://www.shido.info/lisp/pacl2.html
に回答を載せている方がいらっしゃったので、参考にさせてもらいました。


aの回答ですが、CMUCLでは、

Attempt to modify the locked package COMMON-LISP, by redefining function CONS

と出てしまったので、my-consに変更。

(defun my-cons (x y)
  (let ((ls '(nil . nil)))
    (setf (cdr ls) x
          (car ls) y)
    ls))

(format t "cons = ~A~%" (cons 'a '(b c d)))
(format t "my-cons = ~A~%" (my-cons 'a '(b c d)))

結果はこう。

* 
MY-CONS
* cons = (A B C D)
NIL
* my-cons = ((B C D) . A)
NIL
* 

なんか違うような。。
意味が分からないので、6は飛ばし。(誰か分かる方教えてください。)

7. 図3.6のプログラムを改変して使用するコンスセルが少なくなるようにせよ。(ヒント:ドットリストを使う)

コンスセルってなんだっけ? と思ったらコンスのことらしい。なんだ。
そしてまたも回答例を見てしまう。うーん、がんばれよ > 俺


n-eltsの定義を変えるだけか。

((3 1) 0 1 (4 0) 1)

って返ってくるのが、

((3 . 1) 0 1 (4 . 0) 1)

って返ってくるように変わる。


箱表記するとこんな感じ?

この例の場合、使用するコンスセルが9個から7個に減ったと言えるのだと思われます。

8. 1つのリストを引数としてドット表記で表示する関数を定義せよ。

(defun print-list-by-dotted-format (lst)
  (if (null lst)
    (format t "NIL")
    (or (format t "(~A . " (car lst))
        (print-list-by-dotted-format (cdr lst))
        (format t ")"))))

(print-list-by-dotted-format '(a b c))

結果はこう。

* 
PRINT-LIST-BY-DOTTED-FORMAT
* (A . (B . (C . NIL)))
NIL
* 

9. 3.15節に示したネットワークで最長経路(同じ部分は1度しか通らない)を発見するプログラムを書け。ネットワークは循環部分を含むかもしれない。

これは難しいなあ。弱いけど、いったんパス。
つか、まだ3章なのにこの調子で大丈夫なのか?