ITコンサルの日常

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

「ANSI Common Lisp」2章練習問題

Lisp

長いので別エントリにしてみる。

1. 以下の式が評価されたとき何が起こるかを説明せよ。

やってみればいいじゃん。

* (+ (- 5 1) (+ 3 7))

14
* (list 1 (+ 2 3))

(1 5)
* (if (listp 1) (+ 1 2) (+ 3 4))

7
* (list (and (listp 3) t) (+ 1 2))

(NIL 3)
*

ということで、まあ予想通り。

2. (a b c)を返すcons式を3通り示せ。

(cons 'a '(b c))
(cons 'a (cons 'b '(c)))
(cons 'a (cons 'b (cons 'c ())))

結果はこう。

* 
(A B C)
* 
(A B C)
* 
(A B C)
*

3.carとcdrを使って、リストの4番目の要素を返す関数を定義せよ。

(defun our-fourth (lst)
  (car (cdr (cdr (cdr lst)))))

(our-fourth '(a b c d e))

結果はこう。

* 
D
*

4.2つの数を引数として、大きい方を返す関数を定義せよ。

大きい方って、同じ場合はどうするんでしょうね。
とりあえずnilを返すようにしてみました。

(defun larger (a b)
   (if (> a b)
     a
     (if (> b a)
       b
       nil)))

(larger 1 2)
(larger 4 3)
(larger 6 6)

結果はこう。

* 
LARGER
* 
2
* 
4
* 
NIL
*

5.以下の関数は何をするものであろうか。

(a)

(defun enigma (x)
  (and (not (null x))
     (or (null (car x))
         (enigma (cdr x)))))

何もしないが正解な気がする。

(b)

(defun mystery (x y)
  (if (null y)
    nil
    (if (eql (car y) x)
      0
      (let ((z (mystery x (cdr y))))
        (and z (+ z 1))))))

うーん。ムズいなあ。
動かしてみた感じ、リストyの中にxが見つかった場合、その位置(0オリジン)を返すという関数らしい。
見つからない場合はnilが返ってくる。

(mystery 1 ())
(mystery 1 '(1 2 3 4))
(mystery 2 '(1 2 3 4))
(mystery 3 '(1 2 3 4))
(mystery 9 '(1 2 3 4))

結果はこう。

* 
MYSTERY
* 
NIL
* 
0
* 
1
* 
2
* 
NIL
*

6.以下のそれぞれの応答でxは何をしているか。(xはどんなオペレータで置換すればよいだろう。)

(a)

 * (car (x (cdr '(a (b c) d))))

B

これはcarでしょう。

 * (car (car (cdr '(a (b c) d))))

B
 * 
(b)

 * (x 13 (/ 1 0))

13

(/ 1 0)が評価されると
Arithmetic error DIVISION-BY-ZERO signalled.
になってしまうので、そこにいかせないようにする必要がありますね。
ということでorかな。

 * (or 13 (/ 1 0))

13
 * 
(c)

 * (x #'list 1 nil)

(1)

#'listはオブジェクトとしてのlist関数なので、これを呼ぶにはapplyを使います。

 * (apply #'list 1 nil)

(1)
 *

7.本章で導入したオペレータだけを使い、1つのリストを引数とし、そのリストの要素にリストが含まれる場合に真とする関数を定義せよ。

(defun include-list (lst)
  (if (null lst)
    nil
    (if (listp (car lst))
      t
      (include-list (cdr lst)))))

(include-list '(a b c d))
(include-list '(a '(b c) d))

結果はこう。

* 
INCLUDE-LIST
* 
NIL
* 
T
*

最初のnullのテストを入れておかないと、再帰の最後に空リストになって、listpでリストであると判定されてしまうのでなにやってもtになってしまうというオチになります。。

8.以下のような関数を反復と再帰の2通りの方法で定義せよ。

(a)正の整数を引数とし、その数のドット(ピリオド)を表示する。
(defun print-period-loop (n)
  (do ((i 1 (+ i 1)))
      ((> i n) 'done)
      (format t ".")))

(defun print-period-recursive (n)
  (if (> n 0)
    (or (format t ".")
        (print-period-recursive (- n 1)))
    nil))

(print-period-loop 5)
(print-period-recursive 6)

結果はこう。

* 
PRINT-PERIOD-LOOP
* 
PRINT-PERIOD-RECURSIVE
* .....
DONE
* ......
NIL
*
(b) 1つのリストを引数とし、aというシンボルがいくつあるかを返す。
(defun search-a-loop (lst)
  (let ((result 0))
    (dolist (obj lst)
       (if (eql 'a obj)
         (setf result (+ result 1))
         nil))
  result))

(defun search-a-recursive (lst)
  (if (null lst)
     0
     (if (eql 'a (car lst))
       (+ 1 (search-a-recursive (cdr lst)))
       (search-a-recursive (cdr lst)))))

(search-a-loop '(a b c a d))
(search-a-recursive '(a b c a d))

結果はこう。

* 
SEARCH-A-LOOP
* 
SEARCH-A-RECURSIVE
* 
2
* 
2
*

9.友人が1つのリスト中のnilでない要素の合計を返す関数を書こうとしている。彼はこの関数について2通りのプログラムを書いたが、どちらも正しく動かない。それぞれについて間違っている点を説明し、正しいプログラムを示せ。

(a)

(defun summit (lst)
  (remove nil lst)
  (apply #'+ lst))

remove関数はlstに副作用を及ぼさないため、(apply #'+ lst)のlstは、removeされる前のlstのままである。よって、remove関数の戻り値を利用するように変更する。

(defun summit (lst)
  (apply #'+ (remove nil lst)))

(summit '(1 nil 4 nil 5))

結果はこう。

* 
SUMMIT
* 
10
* 
(b)

(defun summit (lst)
  (let ((x (car lst)))
    (if (null x)
      (summit (cdr lst))
      (+ x (summit (cdr lst))))))

空リストの考慮が抜けているようなので、lstのnilチェックを行うようにする。
そのまま実行してみたら、無限ループに入ったようで応答がなくなりました。。

(defun summit (lst)
  (if (null lst)
    0
    (let ((x (car lst)))
      (if (null x)
        (summit (cdr lst))
        (+ x (summit (cdr lst)))))))

(summit '(1 nil 4 nil 3))

結果はこう。

* 
SUMMIT
* 
8
*