BlockSorting を Groovy で

今年も半分が終わろうとしているが1月の TODO を解決する。

• 404 Blog Not Found:Algorithm - Suffix Array を JavaScript で再発明してみた

Suffix Array ではなく BWT の方を。

Groovy で実装してみる

参考

• http://homepage3.nifty.com/DO/blocksorting.htm
• BlockSorting - 西尾泰和のはてなダイアリー
• 続・BlockSorting(BWT) - 西尾泰和のはてなダイアリー
• BlockSorting を Squeak Smalltalk で - Smalltalkのtは小文字です

Ruby 版をそのまま Groovy へ

def encode(src) {
  int n = src.size()
  def srcsrc = src + src
  def vars = (0..<n).collect{ srcsrc[it..<it+n] }
  def code = vars.sort(true).collect{ it[-1] }
  return [code.join(), vars.indexOf(src)]
}

def decode(code, int index) {
  int n = code.size()
  def pairs  = [code.toList(), 0..<n].transpose()
  // stable sort
  def sorted = pairs.sort{ a, b -> a[0] <=> b[0] ?: a[1] <=> b[1] }
  def result = []
  n.times{
    result << sorted[index][0]
    index   = sorted[index][1]
  }
  return result.join()
}

assert encode("abracadabra") == ["rdarcaaaabb", 2]
assert decode("rdarcaaaabb", 2) == "abracadabra"

BWT とは？

Burrows-Wheeler Transform の略でブロックソートとも呼ばれているみたい。
圧縮前に行う変換処理で BWT 自体は圧縮しないが、圧縮しやすいように並べ替えてくれる。
先程実装したものを使って確認してみる。

assert encode("abcabc") == ["ccaabb", 0]
assert encode("abccba") == ["bacacb", 1] 

1つ目のようにパターンに同じようなパターンが表れると変換後連続するようになる。
2つ目のような場合はばらばらのまま。
不思議なことにこの変換後の文字列と数値から元の文字列へ戻すことができる。

どうして decode できるのか？

Wikipedia の説明が分かりやすいのそっちを読んだ方がいいかも

• ブロックソート - Wikipedia

ここでは、例としてよくない気がするが "abcde" を変換する様子を見ていく。

巡回行列をつくる。

def matrix = [
  "abcde",
  "eabcd",  // 1行目を rotate 1
  "deabc",  // 2行目を rotate 1
  "cdeab",  // 3行目を rotate 1
  "bcdea"   // 4行目を rotate 1
]

第1列でソートする。
第1列でソートしたとき最終列は e,a,b,c,d である。
これが encode の戻り値でもう1つの戻り値の数値は元の文字列の行インデックスを返している。

assert matrix.sort{ it[0] } == [
  "abcde",
  "bcdea",
  "cdeab",
  "deabc",
  "eabcd"
]

assert encode("abcde") == ["eabcd", 0]

他の列でもソートしてみる。
巡回しているのでソートした列の1つ前の列は e,a,b,c,d である。

// 第2列でソートしたとき第1列は e,a,b,c,d である
assert matrix.sort{ it[1] } == [
  "eabcd",
  "abcde",
  "bcdea",
  "cdeab",
  "deabc",
]
// 第3列でソートしたとき第2列は e,a,b,c,d である
// 第4列でソートしたとき第3列は e,a,b,c,d である
// 第5列でソートしたとき第4列は e,a,b,c,d である

この性質を使って、最終列の文字列から巡回行列をソートした状態をつくることができる。

// 1. 第1列を e,a,b,c,d にし、第2列をソートされた文字列にする
matrix = [
  "ea...",
  "ab...",
  "bc...",
  "cd...",
  "de...",
]

// 2. 第1列でソートする。最終列は、e,a,b,c,d になるはず
matrix = [
  "ab..e",
  "bc..a",
  "cd..b",
  "de..c",
  "ea..d",
]

// 3. 全行 rotate 1 すれば 1. に戻る

巡回行列をソートした状態の何番目に元の文字列があるかはわからないのでインデックスを使う。

ソートを1回だけにする

先程の工程をそのまま実装すると n 回のソートが必要になる

def process1(input) {
  def n = input.size()
  def output = [[]] * n
  n.times {
    output = [input, output].transpose().sort{ it[0] }.collect{ h, t -> [h, *t] }
  }
  return output
}

同じ文字列をソートしているので、すべてのソートは同じ変換になる。
巡回しているのでそれ以降が既にソートされていることも重要である。
このためソートは常に安定ソートになる。
ソートで行う行の入れ替えを transform に覚えておけばソートは1回で済む。

def process2(input) {
  def n = input.size()
  def output = [[]] * n
  def transform = [input, 0..<n].transpose().sort{
    a, b -> a[0] <=> b[0] ?: a[1] <=> b[1]
  }.transpose()[1]
  n.times {
    output = [input, output].transpose()
    output = (0..<n).collect{ output[transform[it]] }.collect{ h, t -> [h, *t] }
  }
  return output
}

最終的な行番号が分かっていれば、その行だけ変換するようにできる。

// trace は対象行だけの処理を行う
def process3(input) {
  def n = input.size()
  def transform = [input, 0..<n].transpose().sort{
    a, b -> a[0] <=> b[0] ?: a[1] <=> b[1]
  }.transpose()[1]
  def trace = { i ->
    def result = []
    n.times{
      i = transform[i]
      result << input[i]
    }
    return result
  }
  return (0..<n).collect{ trace(it) }
}

assert process1("rdarcaaaabb" as List) == process2("rdarcaaaabb" as List)
assert process1("rdarcaaaabb" as List) == process3("rdarcaaaabb" as List)

decode 時には行番号が分かるのでその行だけ追いかければよい。
これで最初に実装した処理の意味が分かった。

行番号の代わりに終端文字を使う実装

文字列の最後に終端を示す文字を加えておけば、復元した行列から最後が終端文字の文字列が元の文字列であると分かる。
ただし、終端を示す文字は元の文字列に含まれていないこと。

英語版の Wikipedia に載っているものを Groovy で実装してみる。

SEP = '\0'

def bwt(s) {
  assert !s.contains(SEP)
  s += SEP
  def table = (0..<s.size()).collect{ s[it..-1] + s[0..<it] }.sort(true)
  return table.collect{ it[-1] }.join()
}

def ibwt(r) {
  def table = [""] * r.size()
  r.size().times {
    table = (0..<r.size()).collect{ r[it] + table[it] }.sort()
  }
  return table.find{ it[-1] == SEP }.replaceFirst(~/.$/, "")
}

assert "cacao" == ibwt(bwt("cacao"))

参考

• Burrows–Wheeler transform - Wikipedia

Reverse Polish notation calculator

『すごいHaskellたのしく学ぼう!』 の 10章の逆ポーランド記法電卓を Groovy, Scala, Clojure, Scheme で書いてみる。

• Reverse Polish notation calculator

Groovy

def solveRPN(expr) {
  expr.tokenize().inject([]){ acc, v ->
    "*" == v ? [acc[1] * acc[0], *acc.drop(2)] :
    "+" == v ? [acc[1] + acc[0], *acc.drop(2)] :
    "-" == v ? [acc[1] - acc[0], *acc.drop(2)] :
               [v as double,     *acc]
  }[0]
}

assert solveRPN("10 4 3 + 2 * -") == -4.0
assert solveRPN("2 3.5 +") == 5.5
assert solveRPN("90 34 12 33 55 66 + * - +") == -3947.0
assert solveRPN("90 34 12 33 55 66 + * - + -") == 4037.0
assert solveRPN("90 3.8 -") == 86.2
assert solveRPN("") == null

0, 1 の順なら pop でも対応できそうだが、1, 0 の順に参照しなければならないので drop と組み合わせた。
意味はないが空文字が渡されたら null を返すようにしてみた。
関連するメソッドの動作。

groovy:000> "".tokenize()
===> []
groovy:000> "".split()
===> [Ljava.lang.String;@83f700d
groovy:000> [].head()
ERROR java.util.NoSuchElementException:
Cannot access first() element from an empty List
        at groovysh_evaluate.run (groovysh_evaluate:2)
        ...
groovy:000> [][0]
===> null

Scala

val solveRPN: String => Double =
  _.split(' ').foldLeft(List.empty[Double]){
    case (x::y::ys, "*") => (y * x)::ys
    case (x::y::ys, "+") => (y + x)::ys
    case (x::y::ys, "-") => (y - x)::ys
    case (xs, number)    => number.toDouble::xs
  }.head

assert( solveRPN("10 4 3 + 2 * -") == -4.0 )
assert( solveRPN("2 3.5 +") == 5.5 )
assert( solveRPN("90 34 12 33 55 66 + * - +") == -3947.0 )
assert( solveRPN("90 34 12 33 55 66 + * - + -") == 4037.0 )
assert( solveRPN("90 3.8 -") == 86.2 )

Scala はパターンマッチがあるので Haskell と変わらない。
14章に Maybe を使った安全版があるので Scala ならそっちを実装するべきだったかもしれない。
空文字にも対応していない。
split が曲者だった。

scala> "".split(' ')
res0: Array[String] = Array("")

scala> "".split("\\s+")
res1: Array[java.lang.String] = Array("")

scala> """\s+""".r.split("")
res2: Array[String] = Array("")

scala> """\S+""".r.findAllIn("")
res3: scala.util.matching.Regex.MatchIterator = empty iterator

Clojure

(defn solve-rpn [expr]
  (defn f [[x y & ys :as s] w]
    (cond
      (= "*" w) (cons (* y x) ys)
      (= "+" w) (cons (+ y x) ys)
      (= "-" w) (cons (- y x) ys)
      :else     (cons (Double/parseDouble w) s)))
  (->> expr (re-seq #"\S+") (reduce f []) first))

(assert (= (solve-rpn "10 4 3 + 2 * -") -4.0) )
(assert (= (solve-rpn "2 3.5 +") 5.5) )
(assert (= (solve-rpn "90 34 12 33 55 66 + * - +") -3947.0) )
(assert (= (solve-rpn "90 34 12 33 55 66 + * - + -") 4037.0) )
(assert (= (solve-rpn "90 3.8 -") 86.2) )
(assert (= (solve-rpn "") nil) )

パターンマッチはないが分配束縛があるのでそれを使った。
nil 耐性があるので引数の時点で分配している。

user=> (clojure.string/split "" #"\s+")
[""]
user=> (re-seq #"\S+" "")
nil
user=> (first nil)
nil
user=> (first [])
nil

Scheme

(define (solve-rpn expr)
  (define (f v acc)
    (cond
      ((equal? "*" v) (cons (* (cadr acc) (car acc)) (cddr acc)))
      ((equal? "+" v) (cons (+ (cadr acc) (car acc)) (cddr acc)))
      ((equal? "-" v) (cons (- (cadr acc) (car acc)) (cddr acc)))
      (else           (cons (string->number v) acc))))
  (car (fold f '() (string-split expr #/\s+/))))

(solve-rpn "10 4 3 + 2 * -") ;=> -4
(solve-rpn "2 3.5 +") ;=> 5.5
(solve-rpn "90 34 12 33 55 66 + * - +") ;=> -3947
(solve-rpn "90 34 12 33 55 66 + * - + -") ;=> 4037
(solve-rpn "90 3.8 -") ;=> 86.2
(solve-rpn "") ;=> #f

まだ、どんな関数があるのかよく知らない。
今風な API Doc が欲しい。

gosh> (string-split "" #/\s+/)
("")
gosh> (string->number "")
#f
gosh> (car '())
*** ERROR: pair required, but got ()
gosh> (use srfi-1)
#<undef>
gosh> (reduce + 10 '(1 2 3))
6
gosh> (reduce + 10 '())
10

終わりに

簡単そうに思えたが書いてみるといろいろ気づくことがあった。
言語によって微妙に違うので注意したい。

2012-06-11 追記

Clojure 版の f はローカル関数にしたつもりだったがグローバルから参照できてしまった。
defn ではなく letfn を使って f を定義するように修正する。

(defn solve-rpn [expr]
  (letfn [(f [[x y & ys :as s] w]
            (cond
              (= "*" w) (cons (* y x) ys)
              (= "+" w) (cons (+ y x) ys)
              (= "-" w) (cons (- y x) ys)
              :else     (cons (Double/parseDouble w) s)))]
    (->> expr (re-seq #"\S+") (reduce f []) first)))

(assert (= (solve-rpn "10 4 3 + 2 * -") -4.0) )
(assert (= (solve-rpn "2 3.5 +") 5.5) )
(assert (= (solve-rpn "90 34 12 33 55 66 + * - +") -3947.0) )
(assert (= (solve-rpn "90 34 12 33 55 66 + * - + -") 4037.0) )
(assert (= (solve-rpn "90 3.8 -") 86.2) )
(assert (= (solve-rpn "") nil) )

学習

頭の中の灰色の細胞が CPU や HDD だったとする。
知っていることが増えるのは HDD に書き込んだからということにしよう。
しかし、プログラミング能力が向上することを説明するのは難しい。
なぜなら CPU は変わっていないのだから。

考えられるのは HDD の中から似ているコードを検索することだ。
HDD に貯め込んだコードの量が増えるほどプログラミングできる範囲は広がる。
しかし、コードの量が増えるほどプログラミング速度が遅くなってしまいそうだ。
これは観測結果と一致しない。
むしろ広範囲の知識を持っている人の方がプログラミングも速い気がする。
CPU も HDD も優秀な人がいることはわかるが、自分自身でも知識が広がった方が速くなってるのでハード的な問題ではなさそうだ。

認知心理学の知恵を借りる

岡本浩一氏の 『上達の法則』 を読んだところ、知識は 「宣言型知識」 と 「手続き型知識」 の2種類に分けられるらしい。

• 宣言型知識は、円周率は 3.14 のような一般的に 「知識」 と呼ばれるもの
• 手続き型知識は、言葉では言い表せない 「手続き」 を含んだもの

技能の習得にはこの両方が必要で、これらを効率よく記憶、検索、利用できるようになることが上達を意味する。

では初心者と上級者の違いは何なのか？
まず脳には制約があって、脳に存在するワーキングメモリは7個ぐらいの塊で出し入れしなければならない。
上級者は知識を塊に変換する方法の種類が豊富で、かつ塊を小さくできたり大きくできたりするので初心者より出し入れしやすい。
初心者はワーキングメモリのフィルタではじかれるものがあるから同じ技能経験で得られるものも変わってくる。

ここまでが書籍の2章に書かれていた内容

どれくらい違うのだろうか？

塊の認識の違いは、カスパロフ氏の 『決定力を鍛える』 に書かれていた。
人間が計算力でコンピュータに対抗できるのは、意味のある単位にまとめて組合せの数を減らせるからだそうだ。
うまく塊を扱えれば線形的な違いではなくオーダーの違いを得られる。

しかしチェスは何手読めるかで勝敗が決まるわけではないそうだ。
同じ局面を見て黒が有利という人と白が有利という人に分かれる。
計算力と判断力は別の軸らしい。
「計算力の優劣で判断する人を決める」ことは「定規を持っているから長さで決める」ことと似ている。*1

プログラミング自体は大抵答えのある問題を扱っている(実装したい機能や計算したい値がある)はず。
そうするとやはり塊を扱う能力が重要となってくる。
ウサイン・ボルト選手は平均より2倍速いわけではないが1番速い。プログラミング速さは実際どれぐらいなのだろうか？
これは難しい問題らしい。

• 2010-09-27

しかし、アルゴリズムのオーダーと同じように考えるとやはりうまく塊を扱えることがポイントになりそうだ。
塊を扱う単位を変えたところでオーダーが変えられるわけではないが、扱う単位を変えられなければばオーダーは変わらない。

知識の塊の扱い方

これを知りたい。
上級者から教わることがある。
「そこはこの2つセットで考える」 とか 「こっちから見る方法もある」 みたいに。
そうでない場合は、上級者の切り口をみて自分で考えるしかない。
「塊を小さく切り分けているな」 ということは分かっても、どうしてその単位なのかは分からなかったりする。
オーダーの違いや手続き型知識の場合もあるので必ずしも聞いて分かるとは限らない。

世の中には斬鉄剣の使い手のように知識の塊を 「また、つまらぬ物を斬ってしまった」 と簡単に扱える人がいる。
そのような人は大抵のことが遅延学習法で間に合う。一方、斬鉄剣を持っていない人はどういう順序で学ぶべきか？
持っている人より、どうすればオーダーが変わるのか、今のオーダーで十分なものは何かということを意識して選択した方がいいのだろう。
見積もれるわけではないので意識するより具体的な方法を思いつかない。

「なぜ関数プログラミングを学ぶのか？」 という質問に対する個人的な答えは、「知らない切り口があるから」 だ。
もちろん関数プログラミング以外ににも新しい切り口は存在するのでそっちを優先するという選択も考えられる。
必ずしも使うから学ぶわけではないし、今後流行しそうだからでもない。
「現在知っている言語で実装できているのになぜ？」 と考える人は、現在のオーダーで今後も間に合うのか考える必要があるはずだ。

今は、『すごい Haskell たのしく学ぼう!』 を読んでいる。
本になっているのだから宣言型知識として書かれている。
しかし、技術として両輪となる手続き型知識を私はまだ得られていない。
得られていない言い訳を考えてたらこんなことになってしまった。
『初めての人のための LISP』 を読んだときも再帰で考えることに苦労した。
そのときはここを参考にしながら読んでいって何とか14章まで読んだ。

• 初めての人のためのLISP (第1講-第5講) - もうカツ丼はいいよな

その経験があるので、今回も最終的に理解できるだろうぐらいの感覚で読んでいる。
とりあえず、手続き型知識を得られるように訓練しなければならない。

追記

『数学ガール ガロア理論』を読み始めた。

「なるほど！確かに対称式が係数で表せています」テトラちゃんは式を確認して言った。「対称式はいつでもこのように係数で表せるんですね……ところで、こういう変形って、なるほど！って思うんですが、自分では思いつきそうにありません。どうしたらできるようになるんでしょう」
「練習」とミルカさんが即答する。
「そうですか……」とテトラちゃんが言った。

テトラさんはどういう風に練習をすればいいかを聞いているような気がするのだが…
しかし、テトラさんといえば総当りなのだから表を作っておけばよいと思った。
ミルカさんが使ったことがあるテクニックを一覧表にしておいて毎回検索。

知識の塊も多次元テーブルでモデリングしておけばよいだけなのか？
未知の列が追加される場合は仕方がないが、追加されたときに他の軸との交点がどうなるのかを埋める。
そういえば『なぜ関数プログラミングは重要か』でも“新しいデータ型を定義したときにその型を処理する高階関数を書くべきである”と書かれていた。

2012-06-04 追記

発想法とか

• TRIZ――10分以内に「それ、どうやって実現するか」を思いつく方法 (1/3) - ITmedia エンタープライズ
• 体系的な知識・技術を身につけるための学習法について - Kentaro Kuribayashi's blog

コーディングに置き換えたらどうなるのだろう？

プログラム版 20Q が欲しい。
データはたくさんですか？データにランダムアクセスできますか？とか答えているとプログラムが返ってくる。
そう考えるとタグが重要で、勉強の質と量の質はそのためのタグが足りているかどうかだと思った。
子曰く 「勉強したら検索のこと考えてタグ付けなきゃだめだよ。タグを付けていても量がなきゃだめだよ。」
でも違和感ない。

手続き型知識を得られないのは、宣言型知識に十分なタグを付けてないので、他の知識との連動できない状態なんだと思う。
ファンクターを、どうタグ付けしたらいいのかよく分からないから、どう使うのか分からない。
タグ付けできれば今まで同じタグを使っている箇所をファンクターで置き換えることができる。
ただ、分からない理由が分かっても分かったことにはならない。

*1:当然計算力で解決する問題は違う

Learn you a Clojure for Great Groovy!

最近話題のタイトルは、たのしく読んでいる途中（9章に入った)。
その話ではなく、このエントリは Clojure で Ninety-Nine Prolog Problems をやっているときに思いついたもの。

• 1. Prolog Lists - Prolog Site

Ninety-Nine Prolog Problems も Lists のところだけ、現在 Groovy, Haskell, Scala, Prolog, Clojure で解いた。*1
Lists の前半のクライマックスは encode-direct 辺りだが Groovy に較べて Clojure は簡潔に書けてしまう。

;; 1.13
(defn encode-direct [s]
  (for [[n c] (map (juxt count first) (partition-by identity s))] (if (= 1 n) c [n c]) ))
(assert (= [[4 \a] \b [2 \c] [2 \a] \d [4 \e]] (encode-direct "aaaabccaadeeee") ))

これは Haskell の group 関数にあたるものが Clojure に存在するためだ。

Prelude> :m + Data.List
Prelude Data.List> group "aaaabccaadeeee"
["aaaa","b","cc","aa","d","eeee"]

つまり 1.09 の pack が Clojure では

• 参考：partition-by - clojure.core | ClojureDocs - Community-Powered Clojure Documentation and Examples

;; 1.09
(defn pack [s] (partition-by identity s))
(assert (= [[\a \a \a \a] [\b] [\c \c] [\a \a] [\d] [\e \e \e \e]] (pack "aaaabccaadeeee") ))

で、Groovy では *2

// 1.09
def pack(list) {
  if (!list) return []
  list = list.reverse()
  list.tail().inject([[list.head()]]){ acc, v -> acc.head()[0] == v ? [[v,*acc.head()],*acc.tail()] : [[v],*acc] }
}

assert ["aaaa","b","cc","aa","d","eeee"] == pack("aaaabccaadeeee".toList())*.join()

Groovy にも Collection#split という同じインターフェイスのメソッドが存在するが振る舞いが違う。
Groovy の split は、引数のクロージャで true と false に分類しているのに対し
Clojure の partition-by は、引数のクロージャで変換した結果が1つ前のグループと同じかどうかで分類している。

これは便利だ。いつもなら partition-by を実装するところだが Clojure はオープンなので貸してもらうことにする。*3

@Grab(group='org.clojure', module='clojure', version='1.4.0')
@Grab(group='org.apache.commons', module='commons-lang3', version='3.1')
import clojure.lang.Compiler
import clojure.lang.Symbol
import clojure.lang.RT
import static org.apache.commons.lang3.StringUtils.removeEnd
import static org.apache.commons.lang3.StringUtils.splitByCharacterTypeCamelCase


def methodMissing(String name, args) {
  def names = splitByCharacterTypeCamelCase(name)*.toLowerCase()
  if (names[0] == "is") {
    names = names.tail()
    names[-1] = names[-1] + "?"
  }
  return Compiler.eval(Symbol.create(names.join("-"))).invoke(*args)
}

def propertyMissing(String name) {
  // Why?
  // Caused by: java.lang.RuntimeException: Unable to resolve symbol: out in this context
  if (name == "out") return System.out
  return Compiler.eval(Symbol.create(name))
}

def pack(s) {
  partitionBy(identity, s)
}

def encode1(s) {
  map(juxt(count, first), pack(s))
}

def encode2(list) {
  pack(list).collect{ [it.size(),it.head()] }
}

assert ["aaaa", "b", "cc", "aa", "d", "eeee"] == pack("aaaabccaadeeee")*.join()
assert [[4,'a'], [1,'b'], [2,'c'], [2,'a'], [1,'d'], [4,'e']] == encode1("aaaabccaadeeee")
assert [[4,'a'], [1,'b'], [2,'c'], [2,'a'], [1,'d'], [4,'e']] == encode2("aaaabccaadeeee")
assert isZero(0)
// Why?
// groovy.lang.MissingPropertyException: No such property: lang for class: clojure
// assert 'a' == clojure.lang.RT.first("abc")
assert 'a' == RT.first("abc")

encode1 は Groovy でも encode2 のように書けるのでメリットがあるわけではないが他の関数も借りられますよということで書いてみた。
propertyMissing の振る舞いがよく分かっていないので Why? が2箇所発生している。
clojure.lang.RT のメソッドなら直接呼び出すことも可能なようだ。
Symbol を毎回生成して eval しているがこれはキャッシュに保持してもいいかもしれない。
改善点はあると思うが Clojure の関数は Groovy から簡単に呼び出せたよ、ということが言いたかった。

*1:Prolog では 28 がまだだが

*2:Scala も探したけど見当たらない。Scala では foldRight + パターンマッチで切り抜けた

*3:Groovy もオープンだ

関数型パーサー

もうすぐ Haskell の本が出版されるので復習する。
『プログラミング Haskell』 の第8章を今回は Scala(version 2.9.2) で書く。

Scala 的に使った方がいいらしいので Option や Either も勉強する。
Scala の API と以下を参考にしながら書いてみた。

• Java で Either モナド - xuwei-k's blog
• Modegramming Style: Scala Tips / Option - Index
• Modegramming Style: Scala Tips / Either - Index

まずはパターンマッチで

ほとんど変わらないはずだが、書籍よりも Code の Parsing.lhs と parser.lhs の方を参考にした。

• Page Redirection

object Parsers {
  type P[A] = Seq[Char] => Option[(A,Seq[Char])]

  implicit def parserWrapper[A](p: P[A]) = new {
    def >>=[B](f: A => P[B]): P[B] = inp => parse(p, inp) match {
      case None          => None
      case Some((v,out)) => parse(f(v), out)
    }
    def +++(q: P[A]): P[A] = inp => parse(p, inp) match {
      case None => parse(q, inp)
      case x    => x
    }
  }

  def parse[A](p: P[A], inp: Seq[Char]): Option[(A,Seq[Char])] = p(inp)

  def unit   [A](v: A): P[A]    = inp => Some((v,inp))
  def failure[A]      : P[A]    = inp => None
  def item            : P[Char] = inp => inp match {
    case Seq()         => None
    case Seq(v,out@_*) => Some((v,out))
  }

  def many [A](p: P[A]): P[Seq[A]] = many1(p) +++ unit(Seq.empty)
  def many1[A](p: P[A]): P[Seq[A]] = p >>= (v => many(p) >>= (vs => unit(v+:vs)))
  def token[A](p: P[A]): P[A]      = space >>= (_ => p >>= (v => space >>= (_ => unit(v))))

  val sat: (Char => Boolean) => P[Char] =
    p => item >>= (x => if (p(x)) unit(x) else failure)
  val digit      = sat(_.isDigit)
  val lower      = sat(_.isLower)
  val upper      = sat(_.isUpper)
  val alpha      = sat(_.isLetter)
  val alphanum   = sat(_.isLetterOrDigit)
  val char: Char => P[Char] = x => sat(_ == x)
  val string: String => P[String] = {
    case "" => unit("")
    case x  => char(x.head) >>= (_ => string(x.tail) >>= (_ => unit(x)))
  }
  val ident      = lower >>= (x => many(alphanum) >>= (xs => unit(x+:xs)))
  val nat        = many1(digit) >>= (xs => unit(xs.mkString.toInt))
  val int        = (char('-') >>= (_ => nat >>= (n => unit(-n)))) +++ nat
  val space      = many(sat(_.isWhitespace)) >>= (_ => unit())
  val identifier = token(ident)
  val natural    = token(nat)
  val integer    = token(int)
  val symbol: (String => P[String]) = xs => token(string(xs))
}

import Parsers._
lazy val expr: P[Int] = term >>= (t =>
                         (symbol("+") >>= (_ =>
                          expr        >>= (e =>
                          unit(t+e)))
                         ) +++ unit(t))
lazy val term: P[Int] = fact >>= (f =>
                         (symbol("*") >>= (_ =>
                          term        >>= (t =>
                          unit(f*t)))
                         ) +++ unit(f))
lazy val fact: P[Int] = (symbol("(") >>= (_ =>
                         expr        >>= (e =>
                         symbol(")") >>= (_ =>
                         unit(e))))
                        ) +++ natural
val eval = (xs: String) => parse(expr, xs.toSeq) match {
  case Some((n, Seq())) => n
  case Some((_, out))   => sys.error("unused input " + out.mkString)
  case None             => sys.error("invalid input")
}

assert( eval("2*3+4")       == 10 )
assert( eval("2*(3+4)")     == 14 )
assert( eval("2 * (3 + 4)") == 14 )

Option のメソッドを使う

パターンマッチは一覧性にすぐれるのだけれども Option でパターンマッチする場合に決まった形が現れる。
この部分の None => None は何度も書いていると飽きてくる...多分

    def >>=[B](f: A => P[B]): P[B] = inp => parse(p, inp) match {
      case None          => None
      case Some((v,out)) => parse(f(v), out)
    }

というわけで省略してしまう。

    def >>=[B](f: A => P[B]): P[B] =
      inp => parse(p, inp).flatMap{ case (v,out) => parse(f(v), out) }

Some を書かない代わりに flatMap でつなげるだけ。

もう一つの方も x => x は Some(y) => Some(y) なので何かメソッドがありそう。

    def +++(q: P[A]): P[A] = inp => parse(p, inp) match {
      case None => parse(q, inp)
      case x    => x
    }

しかし、Option の API を探してみたがこれと思えるものがなかった。

    def +++(q: P[A])        : P[A] =
      inp => parse(p, inp).toLeft(parse[A](q, inp)).fold(Option(_), identity)

toLeft で一旦 Either に変換して再度 fold で Option に戻している。
おそらく None => None の場合は flatMap で済むのでメソッドにすればよいが、
それ以外の場合は最初から Either を使うのだろう。

Either のメソッドを使う

パーサーの戻り値を Either 型に変更する。
まずはパターンマッチで

  type P[A] = Seq[Char] => Either[Unit,(A,Seq[Char])]

  implicit def parserWrapper[A](p: P[A]) = new {
    def >>=[B](f: A => P[B]): P[B] = inp => parse(p, inp) match {
      case Left(_)        => Left()
      case Right((v,out)) => parse(f(v), out)
    }
    def +++(q: P[A]): P[A] = inp => parse(p, inp) match {
      case Left(_) => parse(q, inp)
      case x       => x
    }

None が Left に、Some が Right に変わっただけ

これを Either のメソッドを使うように変更してみる。

  implicit def parserWrapper[A](p: P[A]) = new {
    def >>=[B](f: A => P[B]): P[B] = inp =>
      parse(p, inp).right flatMap{ case (v,out) => parse(f(v), out) }
    def +++   (q: P[A])     : P[A] = inp =>
      parse(p, inp).left  flatMap{ case _       => parse(q, inp) }
  }

両方とも flatMap になるので読みやすい。
.right や .left は 「Right だったら」や「Left だったら」と読める。

パーサーを生成している部分も変更しなくてはならない。
これも素直に None を Left に Some を Right に書き換えただけ。

  def unit   [A](v: A): P[A]    = inp => Right((v,inp))
  def failure[A]      : P[A]    = inp => Left()
  def item            : P[Char] = inp => inp match {
    case Seq()         => Left()
    case Seq(v,out@_*) => Right((v,out))
  }

item は Seq でパターンマッチしているがこれもパターンマッチでなくすことができる。

  def item            : P[Char] = inp => if (inp.isEmpty) Left() else Right((inp.head,inp.tail))

さらに Either のメソッドを使って

  def item            : P[Char] = inp => Either.cond(!inp.isEmpty, (inp.head,inp.tail), ())

左が Right で右が Left なので少しややこしい。

for 式を使う

調べていたら、第8章を Scala で実装されている方がいた。

• http://www.ayutaya.com/dev/scala/haskell-parser-generator
• http://svc.ayutaya.com/wordpress/2011/04/22/scala-haskell-parser-generato/

パーサーに map と flatMap が実装されていれば for 式が使えるらしい。

object Parsers {
  type P[A] = Seq[Char] => Either[Unit,(A,Seq[Char])]

  implicit def parserWrapper[A](p: P[A]) = new {
    def flatMap[B](f: A => P[B]): P[B] = inp =>
      parse(p, inp).right flatMap{ case (v,out) => parse(f(v), out) }
    def map    [B](f: A => B)   : P[B] = inp =>
      parse(p, inp).right flatMap{ case (v,out) => Right((f(v),out)) }
    def +++   (q: P[A])     : P[A] = inp =>
      parse(p, inp).left  flatMap{ case _       => parse(q, inp) }
  }

  def parse[A](p: P[A], inp: Seq[Char]) = p(inp)

  def unit   [A](v: A): P[A]    = inp => Right((v,inp))
  def failure[A]      : P[A]    = inp => Left()
  def item            : P[Char] = inp => Either.cond(!inp.isEmpty, (inp.head,inp.tail), ())

  def many [A](p: P[A]): P[Seq[A]] = many1(p) +++ unit(Seq.empty)
  def many1[A](p: P[A]): P[Seq[A]] = for (v <- p; vs <- many(p)) yield v+:vs
  def token[A](p: P[A]): P[A]      = for (_ <- space; v <- p;_ <- space) yield v

  val sat: (Char => Boolean) => P[Char] =
    p => for (x <- item; y <- if (p(x)) unit(x) else failure) yield(y)
  val digit      = sat(_.isDigit)
  val lower      = sat(_.isLower)
  val upper      = sat(_.isUpper)
  val alpha      = sat(_.isLetter)
  val alphanum   = sat(_.isLetterOrDigit)
  val char: Char => P[Char] = x => sat(_ == x)
  val string: String => P[String] = {
    case "" => unit("")
    case x  => for (_ <- char(x.head);_ <- string(x.tail)) yield x
  }
  val ident      = for (x <- lower; xs <- many(alphanum)) yield x+:xs
  val nat        = for (xs <- many1(digit)) yield xs.mkString.toInt
  val int        = (for (_ <- char('-'); n <- nat) yield -n) +++ nat
  val space      = for (_ <- many(sat(_.isWhitespace))) yield ()
  val identifier = token(ident)
  val natural    = token(nat)
  val integer    = token(int)
  val symbol: (String => P[String]) = xs => token(string(xs))
}

import Parsers._
lazy val expr: P[Int] = for {
                          t <- term
                          r <- (for {
                            _ <- symbol("+");
                            e <- expr
                          } yield t+e) +++ unit(t)
                        } yield r
lazy val term: P[Int] = for {
                          f <- fact
                          r <- (for {
                            _ <- symbol("*");
                            t <- term
                          } yield f*t) +++ unit(f)
                        } yield r
lazy val fact: P[Int] = (for {
                           _ <- symbol("(")
                           e <- expr
                           _ <- symbol(")")
                         } yield e) +++ natural
val eval = (xs: String) => parse(expr, xs.toSeq) match {
  case Right((n, Seq())) => n
  case Right((_, out))   => sys.error("unused input " + out.mkString)
  case Left(_)           => sys.error("invalid input")
}

assert( eval ("2*3+4")       == 10 )
assert( eval ("2*(3+4)")     == 14 )
assert( eval ("2 * (3 + 4)") == 14 )

flatMap だけでよさそうに思うが map がないとエラーになる。
eval でメソッド使ってないことに気づいたが、ここはパターンマッチの方が見やすいのでこのままにしておく。

ブックマークの整理

ブックマークも無限リストのようなものなので head をつかんだまま続けていると Out of Memory になる。
なので、気分転換に整理してみた。

整理の方法

古い方から順に判断した。
最初から考えていたわけではないが、結果的に4つに別れた。

• カテゴライズして Wiki に書き込んだもの
• 単にブックマークを外したもの
• そのままブックマークしておいてデータとして扱うもの
• 判断できないので再度ブックマークして日付を更新する

カテゴライズする

カテゴライズの基準はいろいろ。
内容まで把握できて詳細に分類できるものから内容はわからないが大雑把にこの辺りかなというものもある。
ここで粒度が細かく気軽に読めそうなものは TODO リストにした。
粒度が大きいものやまだ難解なものはカテゴライズしたままで終わっている。
今後どう処理するか考えなければならない。
ある程度の期間があると情報も重複しまとめられることもあった。

不要になるもの

ライブラリやツール関連が多いかも。
新しいものがでてきたライブラリや逆に主流になったライブラリの情報は不要になる。
主流になったライブラリやツールは必要なときに検索すれば新しい情報がみつかるのでブックマークは必要ない。
はてなもタグと本文で簡単に検索できるようになったので消すべきかは実際に検索してみて確認できる。
検索できて、未来の自分もきっと同じように検索すると思えたら削除した。

リンク切れ

こればっかりは仕方がないのだが一番悲しいパターンだ。
一過性のものなら分からないでもないのだが、なぜなくなったのか分からないものもある。
無常を感じた。

データとして扱う

情報量が多すぎるものがこれにあたる。
いつでも調べられるのではずしてもいいのだが調べると大量に Hit するのでフィルタがかかったものとして残しておく。
例えばレシピのようなもの。

先送りする

まだ理解不足なので必要かどうかの判断を先送りした。
人は習性として選択肢がなくなることを避けるらしいので必要かどうか以外の選択肢があった方が必要なものに絞れる。
迷ったら判断を1年先延ばしにすればよいだけなので。

今後

整理してみて不要になるパターンとかもある感じがした。
それを最初からブックマーク対象から外すようにして、その分観測範囲を広げるてみる。
バッファは1年ぐらいにしようと思う。

2012-05-18 追記

Garry Kasparov 氏の 『決定力を鍛える』 からいくつか引用。
ブックマーク整理しながら読み始めたのだが読み終えた。

私たちは意思決定のプロセスを意識しなければならないが、そのプロセスの実践を通じて直感―無意識の働きが向上していく
...
悪いパターンを正し、よいパターンをさらに改善するには、積極的に自分をもっと知ろうとしなければならない

読みを導くには、創造性と秩序がともに行きわたった状態でなければならないからだ。
いつ慣習を破る必要があるかは、状況と本能が教えてくれる

調子がでないときは整理するようにする。

自分が見たい展開について夢想してみると、それが現実に起こりうると気づくことがある。

マテリアルには、その有用性に応じた価値しかない
行動するための時間が重要となるのは、時間をつかってマテリアルをより有効にできる場合に限られる
一日にあと一時間追加されたら、たいていの人は歓迎するだろうが、刑務所の独房の囚人は喜ばない

有効活用できるものを必要としなければならない。

可能な手段を探すことと、状況を評価することには大きな違いがある

何手も先まで読むのは評価するためであって、何手先まで読むかで評価してはいけない。
読める手数は一流とそうでないプレイヤーであまり差はないらしい。
評価が右と左に分かれているみたいだ。

誤った決断の多くは、とにかく意思決定のプロセスを終わらせたい、決断を迫る重圧から逃れたいという願望に端を発している
これは最悪タイプの性急さ、みずから招く過ちだ。なんとしても避けなければならない。

決断しなければいけないから決断したでは理由にならない。

かつて私が攻撃するのは、それしか知らないからだった
いま私が攻撃するのは、それがもっとも効果的だと知っているからだ

結果は同じでもプロセスが違う。

タルタコワ語録
チェスの対局は三つの段階に分かれている
第一は自分が有利だと願う段階、第二は有利だと信じる段階、第三は負けるとわかかった段階だ

一番目と二番目が逆ならまだいいけど。

プレッシャーにさらされているときに多少の不安を感じるのは、いたって自然なことだ。
新たなチャレンジに対してのんきにかまえるようになったときこそ、心配した方がいいかもしれない
なにもかも簡単そうに思えるとしたら、自分を十分に追い込んでいない、もしくはチャレンジが不足している

自信をつけることと誤りを訂正されることの適切なバランスは、各個人が見つけなければならない
経験からいって、”我慢できるうちは負けろ” は優れた原則だ

順調すぎると落っこちるらしい。

私たちは専門分野で、腕を上げることに重点を置きすぎている
そのため、自分の専門を伸ばす一番の近道が、ほかの分野に強くなることにあっても気がつかない

苦手を克服するのが上達する近道のようなことも書かれていた。

一切の危機を避けようとするのは、かえって危険である場合が多く、
それは往々にして危機を先送りすることにしかならない

難所を得意分野にもってくるといいらしい。

Programming Grails

O'Reilly では Open Feedback Publishing System といって執筆中の書籍にコメントできるらしい(ただし English)。

• Online Feedback Publishing System - O'Reilly Media

というわけで Grails の本が出るみたい(まだ半分も書かれていない)。

• Online Feedback Publishing System - O'Reilly Media

Stack Overflow を見ていると Groovy タグに結構な割合で Grails が混じっているので海外では人気なのかな？
基本的にスクリプトしか書かないので関係ないような気もするけどスクリプトからも使えるっぽい。