今日の一行 2006-04-20 [quiz] 部分木の格上げ
http://oss.timedia.co.jp/index.fcgi/kahua-web/show/ossz/oneline/2006-04-20

「述語と木を与えて，述語を満すラベルの付いた部分木をその親の直ぐの弟にする関数を書け．」という問題。またまた出遅れ気味の回答。この翌日で、逆に部分木を格下げする問題も出題されているけど、こちらはカテゴリがquizではないらしいので手をつけないことにしよう。この問題だけで力尽きたともいう。

(define (lookup subtree pred)
  (let lookup-for-suns ((suns (cdr subtree)))
    (cond ((null? suns) '())
          ((pred (caar suns)) (car suns))
          (else
           (lookup-for-suns (cdr suns))))))

(define (include? subtree pred)
  (let check-for-suns ((suns (cdr subtree)))
    (cond ((null? suns) #f)
          ((pred (caar suns)) #t)
          (else
           (check-for-suns (cdr suns))))))

(define (without-grandchild? tree)
  (or (null? (cdr tree))
      (let without-children? ((suns (cdr tree)))
        (cond ((null? suns) #t)
              ((null? (cdr (car suns)))
               (without-children? (cdr suns)))
              (else #f)))))

(define (extract tree pred)
  (cond ((null? tree) '())
        ((pred (caar tree))
         (extract (cdr tree) pred))
        (else
         (cons (car tree)
               (extract (cdr tree) pred)))))

(define (rankup tree pred)
  (if (without-grandchild? tree)
      tree
      (cons (car tree)
            (let rankup-for-suns ((suns (cdr tree)))
              (cond ((null? suns) '())
                    ((include? (car suns) pred)
                     (cons
                      (cons (caar suns)
                            (extract (cdar suns) pred))
                      (cons (lookup (car suns) pred)
                            (rankup-for-suns (cdr suns)))))
                    (else
                     (cons (rankup (car suns) pred)
                           (rankup-for-suns (cdr suns)))))))))

(define test-tree
  (list 'A (list 'B (list 'F)
                    (list 'G (list 'L)
                             (list 'M)))
           (list 'C (list 'H)
                    (list 'I (list 'N)
                             (list 'O (list 'P)
                                      (list 'Q)))
                    (list 'J))
           (list 'D)
           (list 'E (list 'K))))

(define eq-I? (lambda (x) (eq? 'I x)))

gosh> test-tree
(A (B (F) (G (L) (M))) (C (H) (I (N) (O (P) (Q))) (J)) (D) (E (K)))
gosh> (rankup test-tree eq-I?)
(A (B (F) (G (L) (M))) (C (H) (J)) (I (N) (O (P) (Q))) (D) (E (K)))

いかにも、SICPの前半を読んでいる最中です、という雰囲気のただよう回答にみえる。きをあつかうのは大変だ。

今日も歯医者。消毒だけだと思って気を抜いていたら、また注射があった。でも、昨晩心配していたような痛みもなく、本当によかった。この後は、一ヵ月くらいそのまま歯茎が再生するのをまって、ブリッジかなにかするらしい。歯茎が再生したらこのままでもいいんだけど、それはダメなんだろうな……

先週、奥様が自分の歯医者にいくというのでくっついていって検診してもらったら、レントゲンをとられて奥歯を一本抜くことになった。で、いまさっき抜いてきた。小学校のころいれた銀歯で、ずいぶん前からぐらついていたのは自分でも知ってたんだけど、こういうのってどうしても放置しちゃう。結局、長年の間にクラウンの中はすっかりぼろぼろになっていた。レントゲン写真を見て、自分から「抜いてください」とお願いしたくなるくらい。へたに周りの歯がしっかりしているものだから、かえって痛々しさが目立つ。

歯を抜くのは初めてなので、ここ一週間は夜も眠れないくらいびくついていた。だいたい、人間が痛みに耐えるときは歯をくいしばるものなのに、歯を抜くってことはそれができない。麻酔をかければ痛くないっていうけど、その麻酔の注射を歯茎に射すわけじゃん。麻酔されるまで診察台の上で終始手をきつく握り合わせていたら、先生に「そんなに心配しなくて大丈夫ですよ」といわれてしまった。実際、ほとんど痛くなかった。歯を抜く作業も手際がよくて、すーっと何かが抜けていく感覚だけ。ここ一週間、歯を抜く痛みのイメージトレーニングをひそかに繰り返していたので、脳内で大量のエンドルフィンが生成されていただけかもしれない。もちろん、先生の腕もいいんだと思う。彼の一連の作業の流れを見ていればわかる。抜いた後に再度レントゲン撮影して状態を確認するのも好感がもてる。でも、本当に痛み出すのは麻酔が切れる今晩からだっていうしなあ。幸いなのは、頼みの綱として痛み止めと化膿止めをもらったこと。しかも、ロキソニンとケフラールだった。これならうちに山ほどあるので、使い切ってもちょっと安心。

小島麻由美が好きだ。もう、3月に出た6枚目のアルバムが、すごくいい。

スウィンギン・キャラバン
http://www.amazon.co.jp/exec/obidos/ASIN/B000EAV942/

小島麻由美を聞いたことのない人には、2000年のベストがお勧め。

Me And My Monkey On the Moon�Singles and Outtakes�
http://www.amazon.co.jp/exec/obidos/ASIN/B00005HP68/


このベストの後に出た4枚目は個人的に肌に合わない。この6枚目にして、ようやく戻ってきてくれたみたい。
4枚目は、世間的な評価はいいようだけど、どうにもオサレ風なほんわかエフェクトが強くて好きになれない。録音も不用意に音を詰め込みすぎ。歌詞も斜めな視線を気取りました的だったし。もっとこう、かわいくって異次元な小島麻由美の歌を、モヤモヤしていないソリッドな音で聞きたいわけよ。ひたすらショートケーキとか連呼してほしいわけよ。
6枚目にいたって、ようやくそういう雰囲気に戻ってきてくれた。手放しでよろこばしい。脳内には「らすーとのつーもりでー」がリピートされまくり、チョコレートがとけまくり、トルココーヒーが渦巻いている。
ただ、初期のころに比べて「うまさ」を前に出してきてるのは、やっぱり進化だと思うしかないのかなあ。いまは、「うまさ」が「芸風」を犠牲にしていない、そういうぎりぎりのところにいる気がする。そのぎりぎり感が、このアルバムを傑作たらしめているんだとも思う。でもやっぱり引っかかるんだよなあ。なぜか一曲目にして「また明日ね！」といわれてしまうアルバムの構成とか、初期のころの特徴といっていいと思う「妄想のかたまりな歌詞」を意識的に創作しているように見えてしまうところとか。

社内の雑談で「小島麻由美なんてしらねえよ」と言われてしまったので勢いで書いてはみたけれど、読み返すと批判に見えちゃうな。でも違うよ。とにかく小島麻由美が大好きだってことで。


どうでもいいけど、「トルココーヒー」を聞いていると藤子・F・不二雄の短編の「アン子、大いに怒る」の一場面が思い浮かんじゃう。ちょうどはまっている最中っていうのもあるけど、それにしたってあそこで飲んでいるのはコーヒーじゃなくて紅茶だ。でも、外国土産のいかがわしい飲み物をきわめて日常な場面で飲むっていうところは通じていて、結局そういう「日常→妄想」の境界付近が自分は好きなんだろうと思う。

一区切りついたので、ここ数日たまりまくった Bloglines を眺めていたら、また面白げな問題が話題になっている。例によって乗り遅れ気味。
2回作用させると符合が変わるという性質は、虚数とか、三角関数の微分とか、回転行列（ (0 -1 \\ 1 0) ）とかがあるけど、どれも実数から実数への関数ではない。というわけで、こんないんちきしか思いつきません。

x = sinθ
f(x) = (d/dθ) x

=> 

f(x) = cosθ
f(f(x)) = -sinθ 
        = -x（!?）

こんなのは関数の定義とはいえないわけで。

昨日、Red Bull という話題の清涼飲料水を試しに飲んでみたら、ほんとに眠くならない。それで、一日がんばって仕事をしたら、今朝になって風邪の初期症状が。2つの説明。

• Red Bull は一時的に体力をブーストするだけであり、人間の体力には絶対的な限界があるので、必ずあとでツケを支払うことになる
• Red Bull は本当に体力を増強する。本当は昨日から風邪だったのに、昨日は Red Bull のおかげでなんとかがんばれた

論理の錯誤は無視して、今日のところはもう一本 Red Bull を飲んでがんばらなければならない。
　

昼休みの明けの妥協案。けっきょくカウンタみたいなものを使うことにした。あと、car部が巡回リストを含む場合はチェックできない（これをなんとかしようと考えてたら、もうこんな時間！）。あくまでも、「cdrを追っていくようなプロシージャが停止しないリスト」かどうかを調べるってことで（つまり、今朝の z みたいなものは引っかからない）。

(define (cdr-cycle? x)
  (if (not (pair? (cdr x)))
      #f
      (let R ((x x) (y (cdr x)) (c 0))
        (cond ((null? y) #f)
              ((eq? x y) #t)
              ((< 0 c) (R (cdr x) y (- c 1)))
              (else (R x (cdr y) (+ c 1)))))))

gosh> x
(0 . #0=(1 2 . #0#))
gosh> (cdr-cycle? x)
#t
gosh> y
(0 0 . #0=(1 2 . #0#))
gosh> (cdr-cycle? y)
#t
gosh> z
((0 . #0=(1 2 . #0#)) . 4)
gosh> (cdr-cycle? z)
#f

突っ込みありがとうございます。＞Anonymous
サブリストが巡回しているケースということであれば、昨日の「全巡回リストチェックルーチン」を car と cdr についてチェックするように修正すれば大丈夫そうだけど、はたして問題はそこなんだろうかという不安が残る。

;; ex. 3.19
(define (cycle? x)
  (define (whole-cycle? sub)
    (if (or (null? sub) (not (pair? sub))) 
        #f
        (let R ((y (cdr sub)))
          (cond ((null? y) #f)
                ((eq? sub y) #t)
                (else (R (cdr y)))))))
  (if (or (null? x) (not (pair? x)))
      #f
      (or (whole-cycle? (car x))
          (whole-cycle? (cdr x)))))

gosh> x
(0 . #0=(1 2 . #0#))
gosh> (cycle? x)
#t 

サブリストについては再帰的にチェックしていないので、こうすればまた同じ問題に悩まされる。

gosh> x
(0 . #0=(1 2 . #0#))
gosh> (define z (cons x 4))
((0 . #0=(1 2 . #0#)) . 4)
gosh> (cycle? z)
... 

論理的には、こういう再帰的なチェックをすれば解決するのだと思う。or の評価順序の問題があるので、これはもっとどうしょうもなく停止しないけど。

(define (cycle? x)
  (define (whole-cycle? sub)
    (if (or (null? sub) (not (pair? sub))) 
        #f
        (let R ((y (cdr sub)))
          (cond ((null? y) #f)
                ((eq? sub y) #t)
                (else (R (cdr y)))))))
         (if (or (null? x) (not (pair? x)))
             #f
             (or (cycle? (car x)) (whole-cycle? (car x))
                 (cycle? (cdr x)) (whole-cycle? (cdr x)))))

どうすっかな。根本的な考え方を変更する必要があるのかも。

研究者にとっては問題を解くことじゃなく問題を見つけることが重要な仕事だって、どっかで聞いた記憶がある。僕は研究者ではないけれど、ほかの仕事の多くでも、問題を見つけることは積極的に評価されるべきだと思う。
というわけで、重ねてありがとうございます。＞Anonymous

あー、なんか朝からハイだ。

どうでもいい妄想して勝手に怒りが込み上げてきた。あえて猥褻な言葉を使ってお茶を濁すと、問題を見つけることがビジネスモデルで、それを解くために投入する時間とコストと人材がビジネスポリシー。見つけた問題がセンスない&&周回遅れで、しかもその解決方法が的外れなんだから、誰とは言わないけど終わってる。まったく。

かと思うと、exercise 3.19 のように、(This requires a very clever idea) と補足されているような「とんち問題」もある。問題は、巡回リストかどうか判定するプロシージャを set! とか使わないで書け、というもの。

clever idea がなくても、無限集合の重要な性質を知っていればすぐに思い付く方法がある。その性質というのは、「無限集合は、その部分集合と濃度が等しい」というもの。集合の濃度っていうのは、要素の個数くらいの意味。「無限の個数ってなんだよ」って開き直ったら負けで、「一部分だけ取り出してきたのに元と同じくらいたくさん詰まっているのを無限っていうことにしようぜ、逆に」というのが数学なんだと思う（適当）。なんにせよ、clever idea があるとしたら、それは集合論を思い付いた Cantor のものだ。

とにかく、巡回リストも無限集合みたいなもんなので、その一部分が元のリストと同じだけの要素を持っているっていう性質がある。とくに巡回リストの場合は、cdr を取っていくと、そのうち元のリストと同一（eq? の意味で）になる。必ず。

そこで、こう書ける。

;; ex. 3.19
(define (cycle? x)
  (if (null? (cdr x)) 
      #f
      (let R ((y (cdr x)))
        (cond ((null? y) #f)
              ((eq? x y) #t)
              (else (R (cdr y)))))))

gosh> x
#0=(a b c . #0#)
gosh> (cycle? x)
#t

昨日も今日も定時で帰ってきたので、なんかハイだ。

ページ数かぞえ間違えた。まだ半分いってないや。ようやく3.3節に入ったところ。

実は、3章に入ってしばらく、いまいち面白くなかった。主な原因は、set! の使い方を覚えましょう的な雰囲気にあると思う。語弊のない言い方をすると、set! を通して Scheme を深く理解するきっかけをつかむ、っていうところかなあ。ここから先の解説は、関数型プログラミングというより、「コンピュータから見た（Scheme の）プログラム」なのかもしれない。ああ、そもそもそういう趣旨の書名だったか。

もしかしたら、関数型プログラミングにだけ興味がある人は、2章まで読めば十分なのかもしれない。

もちろん、まったく面白くないわけではない。当たり前だけど。ようするに自分が知らないことを気づかせてくれれば面白いので、たとえば exercise 3.16～3.17 は、リストの本当の姿、つまり cons セルとしての姿を実感させてくれて面白い。

リスト x = (a b c) には、いくつの cons セルがあるか。SICPでは、まずナイーブな方法が例示されている。

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))
(define x (list 'a 'b 'c))

gosh> (count-pairs x)
3

これの何が問題かっていうと、リスト内の cons セルを示している car や cdr がある場合に意図した答えにならないこと。

gosh> (set-car! x (cdr x))
gosh> (count-pairs x)
5

自分は、絵を書かないとわからなかった。最初、x はこうなっている。!は、下向き矢印↓のつもり。

x-->|*|*|-->|*|*|-->|*|/|
     !       !       !
    |a|     |b|     |c|

たしかに、consセルが3つある。ここで、(set-car! x (cdr x)) すると、x のリスト表記は ((b c) b c) になる。絵で書くと、こう。

     ________
     |       !
x-->|*|*|-->|*|*|-->|*|/|
             !       !
            |b|     |c|

これを count-pairs で調べると、2個目の cons セルより後ろを2回数えてしまうので、実際の cons セルは 3 つのままなのに結果が5になる。ちなみに、消えた a については忘れていい。キーワードはガーベジコレクションらしい。

この問題を回避する count-pairs を書けというのが exercise 3.17。同じやつを2回数えなければいいだけなんだけど、「同じ」って何？という哲学的な命題と対峙しなければいけない。実際には哲学ではないので、eq? の本当の意味を理解しているかどうかがポイントになるんだと思う。僕の回答。

;; ex. 3.17
(define (count-pairs x)
  (define aux-pairs '())
  (define (member-eq? c ls)
    (cond ((or (null? ls) (null? (cdr ls)) (null? c)) #f)
          ((eq? c (car ls)) #t)
          (else
           (member-eq? c (cdr ls)))))
  (define (aux-count x)
    (cond ((not (pair? x))
           '())
          ((member-eq? x aux-pairs)
           '())
          (else
           (set! aux-pairs (cons x aux-pairs))
           (append (aux-count (car x))
                   (aux-count (cdr x))))))
  (aux-count x)
  (length aux-pairs))

gosh> (count-pairs x)
3

こんな小さな問題で、やたらにいろいろなことが示唆されているので、やめられない。
これなら、(set-cdr! (cddr x) x) みたいな循環しているリストに対しても、正しい答えが得られる。一見すると終わりがないものにケリをつける方法っていうのは、それだけで魔法みたいで、やっぱりやめられない。

ちなみにこんなことをわざわざ書いているのは、独習で不足しがちな「説明してみることで自分の理解度を確認する」という作業を補っているだけです。Webって本当に便利ですね。したがって、あらゆる記事は、きちんと理解した人間による解説ではありません。

SICP がブームらしい。ということをsumiiさんの日記で確認した。職業がら、その手の「ブーム」には気づいてなきゃいけないんだけど、自分の中でなんとなくブームであることを否定していたような気がする。にしても、いつくらいからブームなんだろう。

自分は、5年くらい前に存在を知ってから「いつかきちんと読んでみたい」と断続的に思いつつだらだらと過ごし、いろいろあって去年の11月頃から一人でねちねちと問題を解き進めている。ちょうどそのころにクレジットの契約ができるようになって amazon で原書を注文することが物理的に可能になった、というのも大きい。

帆船模型を作るみたいに、ゆっくり、とにかく手を抜かずにやってるので、遅い。索引を除くページ数でようやく半分を越えた。内容を考えると、この先のほうが時間がかかるだろうから、今年中には読み終らないんじゃないかなあ。

ここまで来たので、べつにブームが来ようがブームが去ろうが、静かに勉強し続ける。

sumiiさんの一連の記事については、その影響で「ブーム」が去るような気がしないでもないし、何より「次」の教材を示してくれているので、大変うれしい。なんていうか、世の中には勉強することに飢えている非学生な人間が少なからずいると思うので、（信頼できそうな）研究者の方によるこの手の書き込みはとても助かります。

土曜の朝から原因不明の発熱で寝込んでしまった。正確に言うと、土曜の昼前からか。その日の早朝は元気だった。土曜日はタワーレコードまで出かけて行ってCDを買うつもりだったのに。
ようやく熱がひいてきたので、土曜日にできなかったことを片付けることにした。とはいえ、あんまり食べてなくて体力がなく外出はできないので、Amazon なんだけど。
自分にとってタワーレコードは、新宿店がCDを漁るのに魅力的な場所なのであって、だからタワーレコードのWebで買物をしたいわけではない。