nobsun:log
(2003/08/25 18:44:15 PDT) "Teach Yourself Scheme in Fixnum Days"
Dorai Sitaram さんの
"Teach Yourself Scheme in Fixnum Days" を訳しました。著者の承諾を得て
公開しています。
誤訳等がそうとうあるはずですので、気づかれたら是非おしえて下さい。
後半部分はかなり読みずらい訳になっています。これは、私が正確に理解できないまま訳したからです。このあたり、是非、ツッコンでくださいまし。
(2003/08/25 21:07:17 PDT) WiLiKi ページを用意しました。ツッコミなどこちらに書きこんでいただけると嬉しいです。
(2003/06/02 19:10:45 PDT) GHG WiLiki
Gauche Hacking GuideというWiLiKiサイトを作りました。意図は、Gauche のソースコードをハックしたときの記録を公開しようというものです。ソースコードをハックした、あるいは、している、あるいは、しようとしている方がどんどん書き込んでいただけると面白いものができそう。よろしくおねがいします。
……なんか Haskell 版 wiki ができるまでの当座しのぎの WiLiKi サイトが欲しくなってきたんですけど、用意してもらえますか? - shelarcy
(2003/05/25 21:10:01 PDT) SICP の読書会ででた「お題」
以前といたことがあるんですが。。。
- 両替の場合の数を求める問題 (SICP Exercise 2.19) を反復プロセスで解く(末尾再帰)には?
素朴な実装では、以下のようになるけど、末尾再帰にするのは?
(define us-coins '(50 25 10 5 1))
(define uk-coins '(100 50 20 10 5 2 1 0.5))
(define (cc amount coin-values)
(cond ((= amount 0) 1)
((or (< amount 0) (null? coin-values)) 0)
(else
(+ (cc amount
(cdr coin-values))
(cc (- amount
(car coin-values))
coin-values)))))
(cc 100 us-coins) ==> 292
- 末尾再帰版をぱっと思いつきで書いてみました。ただ上の実装にくらべて3倍以上遅いので改善の余地ありかも。 -- koguro(2003/05/27 09:32:54 PDT)
(define (cc2 total arg-list)
(cond ((null? arg-list) total)
((= (caar arg-list) 0)
(cc2 (+ total 1) (cdr arg-list)))
((or (< (caar arg-list) 0) (null? (cdar arg-list)))
(cc2 total (cdr arg-list)))
(else
(cc2 total
`((,(caar arg-list) . ,(cddar arg-list))
(,(- (caar arg-list) (cadar arg-list)) . ,(cdar arg-list))
. ,(cdr arg-list))))))
(cc2 0 `((100 . ,us-coins))) ==> 292
- すごいですねぇこれ。どう読むのかしらん。なぜ解けているのかが追いきれてませんが、最後の cc2 の引数の中で、tree-recursion が起っていそうな雰囲気ですねぇ。-- nobsun(2003/05/29 22:03:41 PDT)
- 評価すべき引数をどんどんリストにつなげていっているのでしょう。
評価方法としては末尾再帰ですが、arg-listが途中でめちゃ長くなりそうですね。
(最初にばーっと展開されてから縮んでゆくのかな)。
基本的に、探索すべき空間は大きさ固定の木なので、
最大でたかだか木の一番深いレベルまでのヒープを使用するのがlower bound
のように思うんですが (いわゆる「パス」を保持する)。--Shiro
- 上のナイーブ版の計算木と同じ形の木をつくっているのかな。--nobsun
- そうです、arg-list に引数を追加していっています。ただ上のソースだとリストの先頭につなげていって、すぐに total に足しこんでしまうのでそれほど arg-list は大きくなりません(上の実行例だと、最長で 6。ちなみに else 節の cc2 で arg-list を組みたてるときに最初と2番目の内容を逆にすると 101 まで大きくなります)。遅いのは、おっしゃっているように tree-recursion が起っているせいだと思います。-- koguro(2003/05/30 19:34:53 PDT)
- 以下が以前書いたものとほぼ同じものです。 何やってんだかよく分りませんねぇ^^; --nobsun
(use srfi-1)
(define us-coins '(1 5 10 25 50))
(define uk-coins '(0.5 2 5 10 20 50 100))
(define (cc3 total-amount coin-values)
(define unit (car coin-values))
(define seq-length (/ total-amount unit))
(define (coin-length coin) (/ (list-ref coin-values coin) unit))
(define (prev-count ls n)
(cond ((null? ls) 0)
((= n 0) (car ls))
(else (prev-count (cdr ls) (- n 1)))))
(define initials (list 1))
(define ones (iota seq-length 1 0))
(define max-coin
(- (length (filter (lambda (c) (<= c total-amount))
(reverse coin-values)))
1))
(define (cc max coin index prevs currs)
(if (> index seq-length)
(if (= max coin)
(car currs)
(cc max (+ coin 1) 1 currs initials))
(let ((count (+ (prev-count prevs (- seq-length index))
(prev-count currs (- (coin-length coin) 1)))))
(cc max coin (+ index 1) prevs (cons count currs)))))
(cc max-coin 1 1 ones initials))
gosh> (cc3 100 us-coins)
292
- 末尾再帰…と言ってよいかどうかわかりませんが、とにかく速い解。ただし、coin-valuesはすべて整数でないとだめです。--(2004-06-01 maeda)
(define (cc4 amount coin-values)
(let ((coins (apply vector (reverse coin-values)))
(x-size (+ 1 (apply max coin-values)))
(y-size (+ 1 (length coin-values))))
(define v (make-vector (* x-size y-size) 0))
(define (address x y) (+ (modulo x x-size) (* y x-size)))
(define (aref x y) (vector-ref v (address x y)))
(define (aset x y val) (vector-set! v (address x y) val))
(do ((y 1 (+ y 1)))
((= y y-size))
(aset 0 y 1))
(do ((x 1 (+ x 1)))
((> x amount) (aref amount (- y-size 1)))
(do ((y 1 (+ y 1)))
((= y y-size))
(aset x y (+ (aref x (- y 1))
(aref (- x (vector-ref coins (- y 1))) y)))))))
gosh> (cc4 100000 us-coins)
66793412685001
A Happy Hacking New Year!
今年もたのしく、Hack,Hack,Hack! -- 2003-01-01
- Shiro: 当地はJSTから19時間遅れで新年を迎えようとしているところです。
そろそろ外が花火でやかましくなって来ました。
Hau`oli makahiki hou! -- 2002/12/31 23:20 HST
- コードの移植をするとき、例えば、SCM 用のコードを Gauche 用にしたいとき
SCM にはあって Gauche にはない手続きが一覧できるなんて機能があるといいですねぇ。
とかいってみる。:-) (2002/03/05 19:02:30 PST)
- だっはっはっは。そこまでやるとするとちゃんとしたデータベースが
要りますな。それともマクロで検索結果の集合演算までやらせてしまおうか…
Shiro (2002/03/05 21:16:23 PST).
WiLiKi source
- WiLiKiのコードは最初は150行程度とのことですが、そのくらいの量のプロトタイプ
コードなら私でも読めるかもしれません。WiLiKi のコードは公開しないのですか。
- FAQ でしたね。さっそく、ダウンロードしてみよう。
- ここを読んで、慌ててFAQに追加したのです -- Shiro
Private questions and wish-list on Gauche
(define b "foo")
(define a b)
とならべるのと
(define a b)
(define b "foo")
とでは、同じ効果であってほしい。
後者はエラーになりますが、これは Scheme の仕様なんだろうか?
- Haskellとかだと引数の評価はlazyですが、Schemeでは(define a b)の時点で
bが評価されてしまいます。これはSchemeの仕様です。 -- Shiro
- そうなんですか。define はプロシージャではない特殊な構文だとおもっていました。
- あ、そうです。defineは特殊構文です。ただ、(define <シンボル> <式>) の
<式>の部分はこのフォームが評価された時点で評価される、と仕様書からは
読めるように思います。-- Shiro
- R5RS を読んでみました。たしかに、§5.2.1 では、define は変数をあらたな
ロケーションにバインドした後、代入処理を行うとの記述で、代入処理の部分は
set! と同じということなんですね。ふーむ。 -- nobsun
- (2002/02/24 22:26:56 PST)
SICP 2nd.ed. の4章で同様の議論をやってますね。
Exercise 4.19 にある式
(let ((a 1))
(define (f x)
(define b (+ a x))
(define a 5)
(+ a 5))
(f 10))
Gaucheで評価してみたところ、
*** ERROR: number required: #<undef>
Stack Trace:
_______________________________________
gosh>
でした。Gaucheではどのような解釈になっているのでしょう。
- これも、Schemeの仕様とは違うけれど、手続きが引数に関してcurry化されると
うれしいなあ。
(define (add a b) (+ a b))
と定義しておくと
(add 1 2) ==> (+ 1 2) ==> 3
は当然として、
(add 1) ==> (lambda (x) (+ 1 x))
ができると何かと便利なんです。
- オプション引数については、対応するのは難しい(というかナンセンス)と思います。
- saturated な引数への適用時 apply の冗長に呼ばれるのはしかたないと思いますし、そのほうが自然な気がします。
- 通常の手続きをcurry化できるとさらに嬉しいなあ(ほとんどおねだりモードだなあ)--nobsun
- (define curried-proc (curry normal-proc)) とか。。。
- Shiro: Scheme:手続きのcurry化 の方に追記しておきました。
Schemeの仕様では無理ですが、Gaucheを拡張することは可能です。
私はあんまり関数型プログラミングをばりばりやったことがないので、
curry化できるとこんなに嬉しいよ、というわかりやすい例とかあったら
教えてくださいな。
- nobsun: 高階関数使う場面では、関数がcurry化されているとlambdaを書かずに
すませられることが多いのではないでしょうか。たとえば、
「複数の集合ssから特定の条件pの要素をもつ集合だけを取り出したい」
ような場合を考えると、指定した条件をみたす要素を指定した集合が含んでいるかどうかを
判定する述語 (have? <条件> <集合>) があれば
(filter (have? p) ss)
と書けます。
(filter (lambda (x) (have? p x)) ss)
と書くより楽です。また、
「特定の集合sが、複数の条件psのどれをとってもその条件をみたす要素を含んでいるかどうか」
を判定する場合、
(all (map (flip have? s) ps))
のように書けます。ここで、all はブーリアンのリストの要素が全て真かどうかを判定
する述語。flipは2引数関数の引数の順を入れ換える高階関数とします。
(define (flip f a b) (f b a))
- 通常の手続きをcurry化するのは、元の手続きの引数の数を知っているという前提
でいいような気がしてきました。ので、元の手続きが2引数であれば、(define (curry2 f)
(lambda (x) (lambda (y) (f x y)))) などを使うのが単純でよいかもしれませんねぇ。
- curry化は本来手続きや関数をすべて一引数とみなすという考え方なので、実行効率はあまり考えないのでしょうねぇ。また、オプション引数とは本質的に相容れないとおもいます。
- ないものねだり(その2): Gaucheの起動オプションで、評価方式を普通のEagerではなくLazyに切り替えられたりするとうれしいなぁ(これじゃ、ぜんぜんSchemeじゃないか。^^;)
Last modified : 2013/04/28 23:03:44 UTC