2011/10/30

foldパターン

flatten

CommonLispで

 ((a . b) (c . d))

というconsリストのリストを

 (a b c d)

というリストに直すコードを書きたいわけ。

この問題、入力が「ネストしたリスト」であれば、つまり ((a b) (c d)) を (a b c d) にする、という問題であれば、Lisp組み込みのリスト処理関数を 使ってほぼワンライナーで書ける。

(defun flatten-nested-list (nlist)
  (if (listp nlist) (mapcan #'flatten-nested-list nlist) (list nlist)))

が、この設問での入力はcdrにリストではなくアトムが来るケースを処理しないと ならない。最後がnilでないリスト (dotted list) というのははみ出し者で、 標準の便利なリスト関数はdotted listを想定してないものが多く、うまく扱えない。 これはむしろcarとcdrに分岐する二分木と考えるのが良い。

二分木を深さ優先で再帰していって、順番に出会ったアトムを数珠つなぎに してゆく、と考えれば、こういうコードになる。(consは尻尾からつないでいかないと ならないので、cdr方向に最初に再帰していることに注意)

(defun flatten-tree (tree)
  (labels ((rec (tree seed)
             (cond ((null tree) seed)
                   ((consp tree) (rec (car tree) (rec (cdr tree) seed)))
                   (t (cons tree seed)))))
    (rec tree nil)))

「途中の計算結果を受け渡しながら、木を深さ優先で再帰してゆく」という制御の流れは、 「計算の初期値seed」と「ひとつの要素と途中結果から新たな途中結果を求める計算proc」 をくくりだせば、パターンとして抽象化できる。

(defun fold-tree-right (proc seed tree)
  (labels ((rec (tree seed)
             (cond ((null tree) seed)
                   ((consp tree) (rec (car tree) (rec (cdr tree) seed)))
                   (t (funcall proc tree seed)))))
    (rec tree seed)))

これを使うと、flatten-treeはワンライナーだ。

(defun flatten-tree (tree) (fold-tree-right #'cons nil tree))

また、例えば「木の中にある数字全ての和を求める」なんてのもワンライナーで書ける。

(defun sum-tree (tree) (fold-tree-right #'+ 0 tree))

(sum-tree '((1 . 2) (3 (4) . 5))) => 15

この、seedで中間結果を回しつつ再帰してゆくパターンはとても良く見かけるので、 慣れておくと便利。

Tags: Lisp, Programming

2011/10/29

詩を読む

KIPOのラジオ番組"Aloha Shorts"で今度詩を読むので、そのリハーサル。 たかだか16行の中に、世界がぎゅっと圧縮されて切り取られてる。面白いなあ。

今回読むのは日本語の定型詩とその英訳なのだけど、定型詩というのは 形に収めるために却って内なる感情の圧力が高まる、ということが、 声に出して読んでみるとよくわかる。リズムがわざと変えてある ところが、抑えていた感情の発露点であったり。(シェークスピアでも、 韻律に従っていないところに「書かれていないアクション」が存在する、 と考えるそうだ)。

今になって、中学高校の国語の先生はこういう面白さを伝えたかったのだなあ、 と思うことは多い。

公開録音は11/6、カヘカのドンキの隣のAtherton Studioにて。無料だけど要予約です。

• ALOHA SHORTS Free Live Taping: WAR! WHAT IS IT GOOD FOR? Sunday, November 06, 2011 6:45 PM

Tag: 芝居

2011/10/26

ピアノレッスン20回目

• 基礎: スケール、アルペジオ MM=144。なんか今日は家で弾いたのより調子良かった。
• Beethoven: Sonata #17 (Op31-2) 第1楽章。AllegroをMM=92で。ダイナミクス、テンポのコントラストgood。テクニカルに不完全な箇所がいくつかあるのでそこを集中してやると良い。速度を上げるのは時間かかるので来週は並行して第2楽章やってみたら。
• 少し時間が余ったのでKapustin Op40-3も。MM=96でやったがちょくちょくつっかえる。家でもMM=108くらいが限界だなあ。132なんて出来るようになるんだろうか。

Tag: Piano

2011/10/26

Ubuntu 11.10 on X60s

とある顧客が11.10にしたというので検証用に手元のX60sをアップグレードしてみた。 10.04LTS->10.10->11.04->11.10という長い旅。

• 最大の問題。サスペンドから復帰しない。これはまだ調査中。
• 10.04ではscimを日本語入力に使っててその設定がずっと残ってたんだけど、IME offなのにlauncherで特定のキーが入らなくなるなどなんかうまく動かなくなった。System Settingsから"Language Support" -> "Language" -> Keyboard input method system を "ibus" に。パネルにキーボードみたいなibusのアイコンが出てくるのでそこからPreferenceを選んで、Input Method に "Japanese - anthy (m17n)" を追加。
• Unityはやっぱり馴染まないなあ。なにかとすぐ最大化したがるのは、最大化して使う人が多いんかね。エディタの横幅は常に80カラムでないと落ち着かない身としては勝手に横幅変えられるのはとても困る。
  • カスタマイズするにはCompiz Config Setting Manager (ccsm)をインストールしないとならない。まあ、Launcherで検索してそのままインストールできるので楽ではある。
  • Unityのグローバルメニュー(AppMenu)を無効にする - 憩いの場 を参考に、ランチャーアイコンを小さく、TopEdgeで勝手に最大化を停止。
    • グローバルメニューについてはちょっと見た目煩わしいけど、メニューは普段使わないし、スクリーンスペースとしては(ウィンドウ自体からメニューが無くなっているので)実質変わらないんだよな。というわけでしばらく様子見。
    • 見た目の煩わしさについては、ccsmから"Ubuntu Unity Plugin" > "Experimental" > "Panel Opacity" をいじって半透明にするとやや緩和される。
  • Launcherから起動した時に勝手に最大化になることがあったが、"Ubuntu Unity Plugin" > "Experimental" > "Automaximize Level" を100にすると良いようだ。
• パネルのユーザのところに"[Invalid UTF-8]"と表示される (Bug #874194)。/etc/login.defsのUID_MINを変えて対応。
• Alt-F1でLauncherを出すと、キーボードフォーカスがLauncherにとられたままになる (他のウィンドウをクリックしてもだめ)。ESCでLancherを引っ込めれば戻るんで、これは仕様なのかな。ちょい分かり辛い。

Tag: Computer

2011/10/24

これどうやってたんだっけな (正規表現・続々)

http://twitter.com/k_takata/status/128592744414318592

http://swtch.com/~rsc/regexp/regexp1.html ではバックトラックNFAでの処理が指数関数的に増える例として、/(?:a?){n}a{n}/ が挙げられているが、鬼車だとそうはならないようだ。n=40でも一瞬で終わる。どの最適化が効いているのだろう。

Gaucheでも確かに指数時間になる。鬼車すげえ。と思ったら、Allegro CLでも一瞬で終わった。あれ? Allegro CLで実装してGaucheでは入れてなかったアルゴリズム的な最適化って何があったっけな。

確かにGaucheの{n,m}の実装は手抜きで、すんごくナイーブなスタックマシン上のバックトラックのコードを生成する。Allegro CLの方は一種のレジスタマシンになってて、しかも与えられた正規表現に最適化されたレジスタマシンを正規表現コンパイル時に生成するようになってるので、定数係数で差が出るのは当然なんだが、アルゴリズムの複雑性は変わらないはずなんだけどな (バックトラックの部分にはスタックを使ってるし)。

またバグのせいで速くなってるなんてことじゃなけりゃいいんだが…いろいろ正規表現を変えて試してみたが、ちゃんと最長一致で結果が出てるので、動作自体は正しいように見える。むむむ…

(追記:2011/10/25 12:54:54 UTC): あ、わかった。思い出した。Allegro CLでは、「繰り返しの中身が空文字列とマッチする可能性がある場合」について特別扱いしてた。

空文字列をεと書くと、 /(?:a?){3}a{3}/ =~ "aaa" は素直なNFAだと、前半部分の繰り返しで a-a-a, a-a-ε, a-ε-a, a-ε-ε, ε-a-a, ε-a-ε, ε-ε-a, ε-ε-ε という全ての組み合わせを試すことになる。

けれど a-a-ε がマッチしなかったら、a-ε-a も ε-a-a も 当然マッチしない。なのでAllegro CLでは a-a-a, a-a-ε, a-ε-ε, ε-ε-ε しか試さない。 これで O(2^n) のパターンが O(n) になる。

したがって、/(?:aa?){n}a{n}/ というパターンにするとこの最適化が効かず、指数時間かかることになる。n=25を過ぎたあたりから急速に重くなる。 鬼車も同じパターンだったので (ruby 1.9.2p290で確認)、多分同じ最適化をやってるんじゃないかと推測。

Tags: Programming, Gauche, Lisp