引数に指定された複数のリストから要素の全ての組み合わせを選択し、各組み合わせに対し、関数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) (…

P22,P23の結果を使う。 P24では、1〜mまでの整数からn個の整数を重複無しに選択する。 P25では、リストをランダムに並べ替える。 ;; P24 (defun lotto-select (n m) (rnd-select (range 1 m) n)) (time (lotto-select 6 49)) ;; => (7 14 37 11 33 43) ;; P2…

multiple-value-bindは使ってみたかっただけです。はい。 ;; P23 (defun nth-and-remove (n list &optional (acc nil)) (if (or (<= n 0) (null list)) (values (car list) (append (nreverse acc) (cdr list))) (nth-and-remove (1- n) (cdr list) (cons (c…

endからstartへ寄せることにより、reverseを省略してみた。 ;; P22 (defun range (start end) (do ((op (if (> end start) #'1- #'1+)) (i end (funcall op i)) (acc '())) ((= i start) (push i acc)) (push i acc))) (range 1 10) ;; => (1 2 3 4 5 6 7 8 …

副作用ばりばりで。 ;; P13 (defun encode-direct (lis) (if (null lis) lis (do ((acc '()) (target (car lis)) (count 1) (l (cdr lis) (cdr l))) ((null l) (reverse (cons target acc))) (if (and (eql target (car l))) (incf count) (progn (push (if …

そろそろPSP版の海腹川背が発売するらしいという情報を もらったので、調べてみた。けっこう、ひどい出来らしい。 ↓http://www32.atwiki.jp/kawasepsp/pages/12.html曰く、 ロープが壁に張り付く ロープが壁にめり込む ロープが壁をすり抜ける etc …海腹川背…