プログラマとプロマネのあいだ

プログラマもやるし、プロマネもやるし、たまに似非アーキとか営業っぽいこともやるITエンジニアがスキルアップの話を中心に日常を綴るブログです。

「Ansi Common Lisp」6章練習問題

1. 60ページのtokensについて、:testと:startを引数としてとる(デフォルトはそれぞれ#'constituent, 0)形に定義せよ。

(defun tokens (str test start)
  (let ((p1 (position-if test str :start start)))
    (if p1
      (let ((p2 (position-if #'(lambda (c)
                                 (not (funcall test c)))
                             str :start p1)))
        (cons (subseq str p1 p2)
              (if p2
                  (tokens str test p2)
                  nil)))
      nil)))

(defun constituent (c)
  (and (graphic-char-p c)
       (not (char= c #\  ))))

(defun tokens-ex6-1 (str &key (test #'constituent) (start 0))
  (tokens str test start))

(tokens "ab12 3cde.f" #'constituent 0)
(tokens-ex6-1 "ab12 3cde.f")

結果はこう。

*
TOKENS
*
CONSTITUENT
*
TOKENS-EX6-1
*
("ab12" "3cde.f")
*
("ab12" "3cde.f")
* 

この辺まじめに読んでないから良く分からないけど、
オリジナルの関数と同じ結果だから、多分合ってるんでしょう。

2. 54ページのbin-searchについて、:key, :test, :start, :endを引数としてとる(それぞれ意味とデフォルトは通常のもの)形に定義せよ。

keyってのが良く分からないけど、多分objのことだと思います。

(defun bin-search (obj vec)
  (let ((len (length vec)))
    (and (not (zerop len))
         (finder obj vec 0 (- len 1) #'eql))))

(defun bin-search-ex6-1 (vec &key key (start 0) (end (- (length vec) 1)) (test #
'eql))
  (let ((len (length vec)))
    (and (not (zerop len))
         (finder key vec start end test))))

(defun finder (obj vec start end test)
  (let ((range (- end start)))
    (if (zerop range)
      (if (funcall test obj (aref vec start))
        obj
        nil)
      (let ((mid (+ start (round (/ range 2)))))
        (let ((obj2 (aref vec mid)))
          (if (< obj obj2)
            (finder obj vec start (- mid 1))
            (if (> obj obj2)
              (finder obj vec (+ mid 1) end)
              obj)))))))

(bin-search 3 #(1 2 3 4 5))
(bin-search-ex6-1 #(1 2 3 4 5) :key 3)

結果はこう。

*
BIN-SEARCH
*
BIN-SEARCH-EX6-1
*
FINDER
*
3
*
3
* 

3. 任意の数の引数をとり、その引数の個数を返す関数を定義せよ。

(defun num-args (&rest args)
  (length args))

(num-args)
(num-args 1)
(num-args '(1 2) 3)

結果はこう。

*
NUM-ARGS
*
0
*
1
*
2
* 

4. most(94ページ)を改変して、リストの上位2つの要素を2値として返すようにせよ。

(defun most (fn lst)
  (if (null lst)
      (values nil nil)
      (let ((first (car lst))
            (second nil))
        (dolist (obj (cdr lst))
          (let ((score (funcall fn obj)))
            (cond ((> score (funcall fn first))
                    (progn (setf second first)
                           (setf first obj)))
                  ((> score (funcall fn second))
                    (setf second obj)))))
        (values first second))))

(most #'length '((a b) (a b c) (a)))

改変っていうか、別の関数を定義したと言ってもいいようなレベルですが、、
結果はこう。

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

5. filter(94ページ)を使ってremove-if(キーワードなし)を定義せよ

(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
        (if val (push val acc))))
    (nreverse acc)))

(defun remove-if-ex6-5 (obj lst)
  (filter #'(lambda (x) (if (eql x obj)
                            nil
                            x)) lst))

(remove-if-ex6-5 3 '(1 2 3 4 5))

結果はこう。

*
FILTER
*
REMOVE-IF-EX6-5
*
(1 2 4 5)
* 

6. 1つの数を引数としてとり、それまでに処理した引数で最大のものを返す関数を定義せよ。

グローバル変数使ってやりました。

(defparameter *max-num* nil)

(defun return-max-i-have-ever-received (num)
  (if (null *max-num*)
    (setf *max-num* num)
    (if (> num *max-num*)
      (setf *max-num* num)
      *max-num*)))

(return-max-i-have-ever-received 2)
(return-max-i-have-ever-received 5)
(return-max-i-have-ever-received 4)
(return-max-i-have-ever-received 7)

結果はこう。

*
*MAX-NUM*
*
RETURN-MAX-I-HAVE-EVER-RECEIVED
*
2
*
5
*
5
*
7
*

7. 1つの数を引数としてとり、直前にその関数が呼び出されたときの引数よりも大きければ真を返す関数を定義せよ。この関数は最初に呼び出されるときはnilを返すものとする。

(defparameter *max-num* nil)

(defun return-t-if-max-number-i-have-ever-received (num)
  (if (null *max-num*)
    (progn (setf *max-num* num)
           nil)
    (if (> num *max-num*)
      (progn (setf *max-num* num)
             t)
      nil)))

(return-t-if-max-number-i-have-ever-received 2)
(return-t-if-max-number-i-have-ever-received 5)
(return-t-if-max-number-i-have-ever-received 4)
(return-t-if-max-number-i-have-ever-received 7)

結果はこう。

*
*MAX-NUM*
*
RETURN-T-IF-MAX-NUMBER-I-HAVE-EVER-RECEIVED
*
NIL
*
T
*
NIL
*
T
*

8. expensiveは0から100までの整数1つを引数として、時間がかかる計算を行う関数であるとする。この関数と同じ結果を返すfrugalを定義せよ。ただし、引数がこれまでに処理していないものである場合にのみ、expensiveを呼び出すものとする。

この問題は、expensive関数に副作用が無いことが前提でしょうね。きっと。

(defun expensive (x)
  (format t "expensive called ~A~%" x)
  (+ x 123))

(defparameter *expensive-called-list* nil)

(defun frugal (x)
  (let ((expensive-result (member x *expensive-called-list* :key #'car)))
    (if expensive-result
      (car (cdr (car expensive-result)))
      (let ((expensive-called-result (expensive x)))
        (push (list x expensive-called-result) *expensive-called-list*)
        expensive-called-result))))


(expensive 2)
(expensive 2)
(frugal 2)
(frugal 2)

結果はこう。

*
EXPENSIVE
*
*EXPENSIVE-CALLED-LIST*
*
FRUGAL
* expensive called 2
125
* expensive called 2
125
* expensive called 2
125
*
125
* 

2回目のfrugalの呼び出しの時には、expensiveが呼ばれずに、結果が返ってきているのが分かります。
関数に副作用がないと、結果をキャッシュできるというメリットもあるのですね。

9. applyと同様の関数で、ただし値を返すまでは、数字表示のデフォルトを8進法とするような関数を定義せよ。

(defun octal-apply (fn lst)
  (let ((*print-base* 8))
    (let ((apply-result (apply fn lst)))
      (progn (format t "apply-result = 0~A~%" apply-result)
             apply-result))))

(octal-apply #'+ '(10 20 30))

結果はこう。

*
OCTAL-APPLY
* apply-result = 074
60
* 

あんまり実用的とも思えないですが。。