;;; Exercise 3.7 [s] Why do you think the leftmost of two keys is the ;;; one that counts, rather than the rightmost.同じキーのキーワードパラメタが複数個指定された場合、左端のキーの値が有効となる理由を問う問題。rest パラメタの値に、キーワ…

;;; Exercise 3.6 [s] Given the following initialization for the ;;; lexical variable a and the special variable *b*, what will be the ;;; value of the let form? (setf a 'global-a) (defvar *b* 'global-b) (defun fn () *b*) (let ((a 'local-a)…

データ構造をプログラムから書き換える問題。 推論に失敗する度に、ツリーが拡張されていく。 ;;; Exercise 3.5 [h] (Exercise in a altering structure.) Write a ;;; program that will play the role of the guesser in the game Twenty ;;; Questions. T…

printの様な関数を作成する。ドット対表記が必要ないところは通常のリスト表記で表示する。結構力業。 ;;; Exercise 3.4 [m] Write a function that, like the regular print ;;; function, will print an expression in dotted pair notation when ;;; nece…

問題ではprincを使えと書いてあるけど、writeで実装した。 せっかくなので作成する関数も元のリストをconsし直して返す様にしてみた。 ;;; Exercise 3.3 [m] Write a function that will print an expression in ;;; dotted pair noteation. Use the bulit-i…

;;; Exercise 3.1 [m] Show a lambda expression that is equivalent to ;;; the above let* expression. You may need more than one lambda. (let* ((x 10) (y (+ x 20))) (list x y)) (funcall #'(lambda (x) (funcall #'(lambda (y) (list x y)) (+ x 20…

引数に指定された複数のリストから要素の全ての組み合わせを選択し、各組み合わせに対し、関数fnを呼び出した結果をリストとして返す関数cross-productを定義する。その結果を使ってcombine-allを再定義する。 ;;; Exercise 2.4 [m] One way of describing c…

r5rsの内容をちょっとコピーしてみる。 ただし、実行するとスタックオーバーフローする。 ;;; Exercise 2.3 [h] Write a trivial grammar for some other language. This can be a ;;; natural language other than English, or perhaps a subset of compute…

未定義の関数は、本家サイトのソース公開ページから探せるはず。章の中でcondを使って定義したgenerateがある。 (defun generate (phrase) "Generate a random sentence or phrase" (cond ((listp phrase) (mappend #'generate phrase)) ((rewrites phrase) …

以前のgenerateは、rewriteの戻り値を分岐条件としていたけど、それだと分かりにくいよね、ちゃんと述語を作ろう。という問題。PAIPの答えでは、non-terminal-pを定義していたので、自分はterminal-symbol-pを定義して解いてみる。当然、あまり変わらない。 …

ベクトルの内積を求める問題。 applyとmapcarですっきり定義できた。 ;;; exercise 1.5 [m] Write a function to compute the dot product of two sequences ;;; of numbers, represented as lists. The dot product is computed by multiplying ;;; corresp…

PAIPの解答そのまま。 PAIPの解答を見てcondのt節の後の式は改行しないで書く慣習であることに気づく。 ;;; exercise 1.4 [m] Write a function that counts the number of times an expression ;;; occurs anywarere whthin another expression. Example: (…

car部のnilは空リストではなく、atom扱いで実装。 ;;; Exercise 1.3 [m] Write a function that counts the number of atoms in an expression. ;;; For example: (count-atoms '(a (b) c)) =>3. Notice that there is something of an ;;; ambiguity in thi…

PAIPのAnswerではexprを使っていたけど、powerの間違いかな。 ここは、O(n)の解答で。負の数にも対応したけど、小数を指定されると無限ループになる。 ;;; Exercise 1.2 [m] Write a function to exponentiate, or raise a number to an integer ;;; power. …

章の途中で定義したlast-nameを改造して、タイトル（っていうんか？）を取り扱えるようにする。 考えられるケースは取り扱えって言っても、どんな慣習があるんでしょう？ 取りあえず例題のケースだけに対応。 ;;; Exercise 1.1 [m] Define a version of last…

L-99もP46以降からPrologの問題そのままになってきた。 取りあえず、この辺りでいったん終了。PAIP本でPrologの実装を調べてくるか。 ;; P54A (defun istree (tree) (cond ((null tree) t) ((not (consp tree)) nil) ((not (= (length tree) 3)) nil) (t (an…

指定した範囲に対するgoldbach conjectureの結果を整形して表示。goldbach-rangeは後の、条件を超える素数の組の数を求める問題のために分離しておいた。 ;; P41 (defun goldbach-range (start end &optional (pred #'identity)) (remove-if #'(lambda (n) (…

P22で定義したrangeと、P31で定義したprime-pを使う。 ;; P39 (defun prime-list (m n) (remove-if-not #'prime-p (range m n))) (prime-list 50 100) ;; => (53 59 61 67 71 73 79 83 89 97)

g000001さんの解法を参考にさせてもらいました。まずは、次の素数を見つける関数next-primeを定義。 例によって、P31のprime-pを使います。 (defun next-prime (n) (if (prime-p (1+ n)) (1+ n) (next-prime (1+ n)))) (next-prime 40) ;; => 41 奇数と2は対…

ACLで動作確認。 P34の実装はconsしまくっている模様。 CL-USER> (time (totient-phi 65535)) ; cpu time (non-gc) 540 msec user, 10 msec system ; cpu time (gc) 130 msec user, 0 msec system ; cpu time (total) 670 msec user, 10 msec system ; real …

L-99の問題文では各素数の演算に対する和になっているけど、どうも積っぽい。参照：http://www.geocities.com/hmaxf_urlcr/euler.htm [音が出るので注意] ;; P37 (defun fold1 (func n lis) (if (null lis) n (fold1 func (funcall func n (car lis)) (cdr l…

;; P36 (defun prime-factor-mult (n) (labels ((append-val (m res) (cond ((null res) (list (list m 1))) ((= m (caar res)) (incf (cadar res)) res) (t (cons (list m 1) res)))) (iter (n m limit res) (cond ((> m limit) (reverse (append-val n res…

整数mに対しcoprimeである整数r (1 P33の結果を使い、直接的に実装。 もっとスマートな方法は、後の問題で議論するらしい。 ;; P34 (defun totient-phi (m) (do ((result 0 (if (or (= n 1) (coprime m n)) (1+ result) result)) (n m (1- n))) ((< n 1) res…

直接的に実装。 本当は、mは1+ではなく、次の素数を返す関数で増加させたいところ。 ;; P35 (defun prime-factor (n) (labels ((iter (n m limit res) (cond ((> m limit) (reverse (cons n res))) ((= (mod n m) 0) (iter (/ n m) m (sqrt (/ n m)) (cons m…

gcdが1を返す整数の組をcoprimeというらしい。 ;; P33 (defun coprime (m n) (= (gcd m n) 1)) (coprime 35 64) ;; => T 日本語では、「互いに素」 以下を参照。 http://homepage3.nifty.com/kanzakijuku/a07.html

これもSICPから。 ;; P32 (defun my-gcd (m n) (cond ((< m n) (my-gcd n m)) ((= n 0) m) (t (my-gcd n (rem m n)))))

SICPの1.2.6から。 ;; P31 (defun square (x) (* x x)) (defun expmod (base exp m) (cond ((= exp 0) 1) ((evenp exp) (rem (square (expmod base (/ exp 2) m)) m)) (t (rem (* base (expmod base (- exp 1) m)) m)))) (defun fermat-test (n) (labels ((t…

P27はリストをグループ分けする問題。 P26で定義したcombinationを流用する。 まずは、9要素のリストを2 3 4の要素に分割する関数 group3をつくる。 その後に、分割パターンをリストとして受け取る関数 groupをつくる。groupは、順番が違うだけで、実質同じ…

サブリストの長さで並び替える。 さらに、サブリストの長さの頻度で並び替える。まずは、sort関数を定義。 (defun my-sort (lis smaller-p &key (key #'identity)) (if (null lis) nil (do ((x (car lis)) (bigger '()) (smaller '()) (l (cdr lis) (cdr l))…

リストからn個の要素を取り出す。 取り得る全てのパターンをリストとして列挙する。 ;; P26 (defun combination (n list) (cond ((or (= n 0) (null list)) nil) ((= n 1) (mapcar (lambda (res) (cons res nil)) list)) (t (append (mapcar (lambda (res) (…