最長重複文字列問題 in Groovy
WEB+DB PRESS Vol.67 の最長重複文字列問題をやってみた。
もう少し前に実装していたのだけど takeWhile 待ちしている間に目的が変わってしまった。
Clojure や Scala では既に実装されている方がおられる。
- WEB+DB PRESS Vol.67の最長重複文字列問題をClojureで解いてみた - やぐブロ
- Scalaで入門 関数プログラミングその２ - hilolihの日記
- 最長重複文字列問題 を scala をつかって解いてみる - Takuya71 のぶろぐ
- http://blog.takeda-soft.jp/blog/show/407
なので参考にしながら Groovy で書いたものを Clojure や Scala に書き換えていった。
Java から Groovy への敷居が低いのは、文法が似ているからだ。
同じことが、関数プログラミングにも言えて、Groovy で関数プログラミングのスタイルで書ければ、他の関数プログラミングスタイルの言語も書けてしまう。
Clojure や Scala を最初から詳しく知る必要はなく、まずは Groovy と行き来できる範囲で使えれば後は自然に覚えられるはず。
問題を少し変えてみる
考えてみるとこのアルゴリズムは文字列である必要がないので数列など他の型にも対応することにした。
そもそも元ネタの Haskell では Char を a に置き換えて Ord a => を追加するだけで対応できてしまう。
他の言語もかくありたい。
Groovy
もう待てないので takeWhile 欲しさに Groovy Version: 2.0.0-beta-3 にバージョンアップした。
一応 takeWhile も実装したので、takeWhile のないバージョンの場合は maxDupStr を実行する際にカテゴリで囲めば動作する。
tails = { xs, acc=[] -> xs.empty ? acc << xs : trampoline(xs.tail(), acc << xs) }.trampoline()
listAsc = { xs, ys -> [xs, ys].transpose().findResult{ it[0] <=> it[1] ?: null } ?: xs.size() <=> ys.size() }
sort = { it.sort(listAsc) }
makePair = { it ? it.collate(2, 1, false) : [] }
calcLen = { it.collect{ xs, ys -> lenstr(xs, ys) } }
lenstr = { xs, ys -> [comlen(xs, ys), xs] }
comlen = { xs, ys -> [xs, ys].transpose().takeWhile{ it[0] == it[1] }.size() }
chooseMax = { it.max{ it.first() } }
extract = { it ? it[1].take(it[0]) : null }
maxDupStr = extract << chooseMax << calcLen << makePair << sort << tails
assert maxDupStr("mississippi".toList()).join() == "issi"
assert maxDupStr([8,10,8,10,12,8,10,8,10,12,8]) == [8,10,8,10,12,8]
異なる型でも動作させるので引数はリストを想定した。
しかし Groovy にはダックタイピングがあるので文字列をリストに変換する必要はないかもしれない。
文字列渡し
class CharSequenceOps { static def head(CharSequence cs) { cs[0] } static def tail(CharSequence cs) { cs[1..<cs.size()] } static def transpose(List css) { GroovyCollections.transpose(css*.asType(List)) } static def takeWhile(List list, Closure pred) { list.findIndexOf{ !pred(it) }.with{ i -> i < 0 ? list : list.take(i) } } } use (CharSequenceOps) { assert maxDupStr("mississippi") == "issi" assert maxDupStr("a") == "" assert maxDupStr("") == null }
惜しいところでだめだった。
head と tail は getAt でも OK なのだが transpose が動作してくれない。
groovy:000> "abc" as List ===> [a, b, c] groovy:000> (List) "abc" ERROR org.codehaus.groovy.runtime.typehandling.GroovyCastException:
Groovy には Java 風のキャストと as によるキャストがあるのだが transpose は Java 風のキャストを使っていたからだ。
Groovy では、文字列も配列もリストも size() で長さが取得できるが、これは分かりやすさだけでなくダックタイピングには重要なことなのだ。
CharSequence にも head や tail があれば、Java の String は List ではないが List のように扱えてしまうから。
扱えなかったので、CharSequenceOps に head と tail を実装し、タプルの意味なら getAt でアクセスするようにした。
マルチメソッド
def maxDupStr(List xs) { extract << chooseMax << calcLen << makePair << sort << tails << xs } // def maxDupStr(List xs) { return { [xs] } >> tails >> sort >> makePair >> calcLen >> chooseMax >> extract << [] } def maxDupStr(String s) { maxDupStr(s.toList())?.join() } maxDupStr = this.&maxDupStr assert maxDupStr("mississippi") == "issi" assert maxDupStr([8,10,8,10,12,8,10,8,10,12,8]) == [8,10,8,10,12,8]
これは Clojure から参考にした対応。
Groovy でクロージャではマルチメソッド (動的なオーバーロード) を定義する方法がない（知らないだけ？）が、メソッドで定義してからクロージャにすればマルチメソッドは有効みたいだ。
Scala からのフィードバック
// Comparator でデフォルト引数を取れることに気づいた listAsc = { xs, ys, i=0 -> xs.size() < i && ys.size() < i ? 0 : xs[i] <=> ys[i] ?: call(xs, ys, i+1) } // trampoline を知った listAsc = { xs, ys, i=0 -> xs.size() < i && ys.size() < i ? 0 : xs[i] <=> ys[i] ?: trampoline(xs, ys, i+1) }.trampoline() // Scala で実装されていた List Comparator を Groovy で実装してみた listAsc = { xs, ys -> [xs, ys].transpose().find{ it[0] <=> it[1] }?.with{ it[0] <=> it[1] } ?: xs.size() <=> ys.size() } // findResult を使うようにした listAsc = { xs, ys -> [xs, ys].transpose().findResult{ it[0] <=> it[1] ?: null } ?: xs.size() <=> ys.size() }
上の2つが以前から使っていたもの。その下が今回知ったもの。
他の言語で実装すると違う実装法を知るチャンスも増える。
なぜ List の Comparator を言語で提供してくれないのかはなぞなのだが。
あとなぜデフォルト引数が取れるか裏もとった。
public static <T> List<T> sort(Collection<T> self, boolean mutate, Closure closure) { List<T> list = mutate ? asList(self) : toList(self); // use a comparator of one item or two int params = closure.getMaximumNumberOfParameters(); if (params == 1) { Collections.sort(list, new OrderBy<T>(closure)); } else { Collections.sort(list, new ClosureComparator<T>(closure)); } return list; }
one or two と書いてあるがこの実装なら three も OK だ。
MaximumNumberOfParameters の存在は以前から知っていたが、なぜ Maximum かは最近知った。
最長重複文字列問題 in Scala
Clojure 編につづき Scala 編へ
Scala は Haskell の多くの関数が用意されているので Haskell からの書き換えるのには有利だ。
def makePair [T](xs: Seq[Seq[T]]) = xs zip xs.tail def comlen [T](p: (Seq[T],Seq[T])) = p.zipped takeWhile(x => x._1 == x._2) size def lenstr [T](p: (Seq[T],Seq[T])) = (comlen(p), p._1) def calcLen [T](xs: Seq[(Seq[T],Seq[T])]) = xs map lenstr def chooseMax[T](xs: Seq[(Int,Seq[T])]) = xs maxBy(_._1) def extract [T](p: (Int,Seq[T])) = p._2 take p._1 def maxDupStr[T <% Ordered[T]](xs: Seq[T]) = extract(chooseMax(calcLen(makePair(xs.tails.toSeq.sorted(seqAsc[T]))))) def seqAsc[T <% Ordered[T]]: Ordering[Seq[T]] = new Ordering[Seq[T]] { def compare(x: Seq[T], y: Seq[T]) = x.view.zip(y).map(p => p._1 compare p._2) .find(_ != 0).getOrElse(x.size.compareTo(y.size)) } assert( maxDupStr("mississippi").mkString == "issi" ) assert( maxDupStr(List(8,10,8,10,12,8,10,8,10,12,8)) == List(8,10,8,10,12,8) ) assert( maxDupStr(Array(8,10,8,10,12,8,10,8,10,12,8)) sameElements Array(8,10,8,10,12,8) )
List の Comparator は最初は trampoline のバージョンを移植したのだが Ideone.com - HKjoN - Online Scala Compiler & Debugging Tool のものを見つけたのでこれを使った。
ただ知らない機能だったので、可視境界を使うように変更した。
Scala でこのような機能を調べるときにどうすればよいか分からないのだが今回は運よくすぐ見つけられた。
Context Bound は 2.8 からの機能なので持っている『Scala スケーラブルプログラミング』には載っていなかったのだ。
implicit conversion
Scala 版はこの時点で文字列で渡すことに成功している。
これは Groovy でいうところのカテゴリの機能が効いているためである。
implicit conversion は Java のオートボクシングのようにラッパー型に変換する機能である。
しかもラッパー型に変換する関数も指定できる。
あるスコープ内だけ使えるメソッドが増えるという意味では Groovy のカテゴリと同じ効果がある。
implicit conversion の効果は Groovy のカテゴリなのだが、個人的なイメージではダックタイピングのように思える。
- 同じ名前のメソッドがあれば同じように扱っていいだろう
- ある型に変更してもよいなら変更して扱ってもいいだろう
ラッパー型と変換する関数を用意するのでいまいちオープンクラスと同じといわれてもピンとこないのだがそれっぽいものを見つけた。
変換関数で特異オブジェクトを生成する方法
しかしバージョン 2.10 ではラッパー型自体で変換できるみたいだ。
ただ今回は == は Any のメソッドで String 型を要求されないので mkString が必要になった。
関数プログラミングっぽくない？
Scala 版、関数合成つかってなくない？
合成しようと思えばできますとも。
def maxDupStr[T <% Ordered[T]](xs: Seq[T]) = (extract[T] _ compose chooseMax[T] compose calcLen[T] compose makePair[T])(xs.tails.toSeq.sorted(seqAsc[T]))
メソッドの中で合成するのですか？それはポイントフリースタイルではありません。
それは = の左から xs を消せということですか？
できますとも！
val makePair = (xs:Seq[Seq[Any]]) => xs zip xs.tail val comlen = (p:(Seq[Any],Seq[Any])) => p.zipped takeWhile(x => x._1 == x._2) size val lenstr = (p:(Seq[Any],Seq[Any])) => (comlen(p), p._1) val calcLen = (xs:Seq[(Seq[Any],Seq[Any])]) => xs map lenstr val chooseMax = (xs:Seq[(Int,Seq[Any])]) => xs maxBy(_._1) val extract = (p:(Int,Seq[Any])) => p._2 take p._1 val maxDupStr = extract compose chooseMax compose calcLen compose makePair assert( maxDupStr("mississippi".tails.toSeq.sorted.map(_.toSeq)).mkString == "issi" )
Scala は静的型付け言語なのです。Any を使わないでいきましょう。
しかし、Char と Int をどうすれば同じように扱えるのですか？
型パラメータを使いましょう。
使いました。大量にコンパイルエラーが発生しました。
存在型がバナナでないことは知っていますが、型パラメータにする方法は知りません。
どうして型パラメータが使えないのか？
Scala には難解な用語がでてきますが要は Java なのです。
Groovy プログラマは Java を知っています。Java で考えればよいのです。
// Comparable で考える interface Comparable<T> // Any と書けるということは Object と書けるということ new Comparable<Object>() { @Override int compareTo(Object a, Object b) { ... } } // こんな風には Java でも書かない new Comparable<T>() { @Override int compareTo(T a, T b) { ... } }
T で書くにはどうすればよいでしょう？
// 型ではなく式で考える { 2*it }(1) // 定数ではなく変数を使いたいとしたら { 2*it }(x) // こうするしかない { x -> { 2*it }(x) }
クラスを使って型を遅延評価する
class SeqOps[T] { val makePair = (xs:Seq[Seq[T]]) => xs zip xs.tail val comlen = (p:(Seq[T],Seq[T])) => p.zipped takeWhile(x => x._1 == x._2) size val lenstr = (p:(Seq[T],Seq[T])) => (comlen(p), p._1) val calcLen = (xs:Seq[(Seq[T],Seq[T])]) => xs map lenstr val chooseMax = (xs:Seq[(Int,Seq[T])]) => xs maxBy(_._1) val extract = (p:(Int,Seq[T])) => p._2 take p._1 val maxDupStr = extract compose chooseMax compose calcLen compose makePair } def seqAsc[T <% Ordered[T]]: Ordering[Seq[T]] = new Ordering[Seq[T]] { def compare(x: Seq[T], y: Seq[T]) = x.view.zip(y).map(p => p._1 compare p._2) .find(_ != 0).getOrElse(x.size.compareTo(y.size)) } { val charOps = new SeqOps[Char] import charOps._ assert( maxDupStr("mississippi".tails.toSeq.sorted.map(_.toSeq)).mkString == "issi" ) } { val intOps = new SeqOps[Int] import intOps._ assert( maxDupStr(List(8,10,8,10,12,8,10,8,10,12,8).tails.toSeq.sorted(seqAsc[Int]).map(_.toSeq)) == List(8,10,8,10,12,8) ) }
これで型安全な合成ができるようになった。
Scala の import は、オブジェクトも import できる。これは Groovy の with に近い。
ただし import new とは書けなかった。
毎回、インスタンスを生成する必要はないので保存場所をさがす。
Scala には static がないのでシングルトンオブジェクトを利用する。
object SeqOps { val charOps = new SeqOps[Char] val intOps = new SeqOps[Int] } { import SeqOps.charOps._ assert( maxDupStr("mississippi".tails.toSeq.sorted.map(_.toSeq)).mkString == "issi" ) }
2012-05-12 修正
maxDupStr を SeqOps の中に入れた
2012-05-18 追記
object SeqOps { object Char extends SeqOps[Char] object Int extends SeqOps[Int] }
武田氏の赤黒木を見ていたら StringTree を object で宣言されていた。
型なので大文字ではじめられるように object で宣言した方がいいかもしれない。
最長重複文字列問題 in Clojure
Clojure を学ぶ
Groovy と Scala は Java の文化圏から生まれたものだが、Clojure は Lisp の文化圏から Java に入ってきたものだ。
関数の呼び出しが (関数名 引数1 引数2 ...) と前置記法で書いたリストであるところは Lisp だが、他の Lisp 系言語に比べると Groovy よりである。
今回は関数プログラミングのスタイルなので無名関数の書き方から Groovy と比較してみる
無名関数の書き方
| Groovy | Clojure |
|---|---|
| { x -> 2 * x } | (fn [x] (* 2 x)) |
| { x -> 2 * x } | #(* 2 %) |
| { 2 * it } | #(* 2 %) |
| { x, y -> x + y } | (fn [x y] (+ x y)) |
| { x, y -> x + y } | #(+ %1 %2) |
| { it[0] + it[1] } | #(+ (first %) (second %)) |
- 引数が1つならその引数
- 引数が複数なら引数リスト
Clojure の暗黙のパラメータ % は最初の引数を表わす。
- % と %1 は同じ意味
リストとベクタ
| Groovy | Clojure |
|---|---|
| new ArrayList(){{ add(1);add(2);add(3) }} | (list 1 2 3) |
| [1,2,3] | (quote (1 2 3)) |
| [1,2,3] | '(1 2 3) |
| [1,2,3] | '(1,2,3) |
| [1,2,3] | [1 2 3] |
| [1,2,3] | [1,2,3] |
ベクタの特典
さらにうれしいことにベクタにはもれなく特典がついてくる。
| Groovy | Clojure |
|---|---|
| [1,2,3][0] | ([1,2,3] 0) |
無名関数の呼び出しと apply
| Groovy | Clojure |
|---|---|
| { x, y -> x + y }(1,2) | (#(+ %1 %2) 1 2) |
| { it[0] + it[1] }([1,2]) | (#(+ (first %) (second %)) [1,2]) |
| { it[0] + it[1] }([1,2]) | (#(+ (% 0) (% 1)) [1,2]) |
| { x, y -> x + y }(*[1,2]) | (apply #(+ %1 %2) [1,2]) |
| { x, y -> x + y }([1,2]) | (apply #(+ %1 %2) [1,2]) |
前置記法のメリット
assert [6,6,6].collect{ it + 1 } == [7,7,7] assert [[1,2,3],[6,5,4]].transpose().collect{ it[0] + it[1] } == [7,7,7]
Groovy の場合は、1つのリストと複数のリストで処理が変わる。
;; いくつでもリストを渡せる (map #(+ % 1) [6,6,6]) ;=> (7 7 7) (map #(+ %1 %2) [1,2,3] [6,5,4]) ;=> (7 7 7) ;; 関数呼び出しの形が決まっているので関数だけ渡せばよい (map inc [6,6,6]) ;=> (7 7 7) (map + [1,2,3] [6,5,4]) ;=> (7 7 7)
部分適用
def incinc = { x, y -> x + y }.curry(2) assert [5,5,5].collect(incinc) == [7,7,7] assert [5,5,5].collect(2.&plus) == [7,7,7] // メソッドクロージャ
関数だけ必要な場合が多いので Groovy より部分適用が役に立つ。
(map (partial + 2) [5,5,5]) ;=> (7 7 7)
左から右演算子
Lisp の場合、前置記法はいいのだが入れ子になるのが問題なのだ。
しかし、Clojure では (->> 引数1 関数1 関数2 ...) と書くと (関数1 引数1) を実行した結果を関数2に...という風につなげられる。
これはほとんど obj.method1.method2 という意味なので Groovy に近い。
実際に文字を連結する。バックスラッシュで始まるのが文字リテラル。Groovy には文字リテラルはないが...
;; 文字 \a を文字列にする (str \a) ;=> "a" ;; 左から順に処理を行う (->> \a str) ;=> "a" ;; あらかじめ括弧があってもよい (->> \a (str)) ;=> "a" ;; ->> は引数の最後に追加する (->> \a (str \b)) ;=> "ba" ;; -> は引数の先頭に追加する (-> \a (str \b)) ;=> "ab" ;; 関数は複数並べておくことができる (-> \a (str \b) (str \c)) ;=> "abc" ;; これより読みやすい (#(str (str % \b) \c) \a) ;=> "abc"
その他
真偽値で偽になるのは false, nil だけということは覚えておかないといけない。
個々の関数は調べるしかない。
Clojure は Scala と比べるとそれほど関数が多くなくドキュメントも調べやすい。
Other version には jQuery を使ったリッチなものや PDF もある。
実装してみる
(defn tails [xs] (take (inc (count xs)) (iterate rest xs))) (defn seq-asc [xs ys] (if-let [non-zero (some #(when (not= 0 %) %) (map compare xs ys))] non-zero (compare (count xs) (count ys)))) (defn make-pair [xs] (partition 2 1 xs)) (defn comlen [xs ys] (count (take-while #(apply = %) (map vector xs ys)))) (defn lenstr [xs ys] (vector (comlen xs ys) xs)) (defn calc-len [xs] (map #(apply lenstr %) xs)) (defn choose-max [xs] (when (not-empty xs) (apply max-key first xs))) (defn extract [xs] (when (not-empty xs) (apply #(take %1 %2) xs))) (def max-dup-str (comp extract choose-max calc-len make-pair (partial sort seq-asc) tails)) (assert (= "issi" (->> "mississippi" seq max-dup-str (apply str)))) (assert (= (max-dup-str [8,10,8,10,12,8,10,8,10,12,8]) [8,10,8,10,12,8]))
takeWhile 待ちの間に何回か修正して今はこうなっている。
if-let は Groovy の ?: 演算子に近いかと思う。
Clojure でも文字列をリストのように扱うことはできない。
文字列を渡せるようにする
(defmulti max-dup-str class) (defmethod max-dup-str :default [xs] (->> xs tails (sort seq-asc) make-pair calc-len choose-max extract)) (defmethod max-dup-str String [xs] (->> xs seq max-dup-str (apply str))) (assert (= (max-dup-str "mississippi") "issi")) (assert (= (max-dup-str "a") "")) ; (assert (= (max-dup-str "") nil)) AssertionError (assert (= (max-dup-str [8,10,8,10,12,8,10,8,10,12,8]) [8,10,8,10,12,8]))
defmulti と defmethod を使えば引数の型で分岐できる。
class 関数を指定しているので型で分岐しているだけであって他の関数を使えば型以外でも処理を分けられるらしい。
納得いかないのは str の引数が nil でも引数なしでも空文字を返してくる。
そこで調べてみたら Groovy の ?. のようなものがあったのでこれを使ってみた。
(use '[clojure.contrib.core :only (-?>>)]) (defmethod max-dup-str String [xs] (-?>> xs seq max-dup-str (apply str))) (assert (= (max-dup-str "") nil))
nil を回避している理由が若干違うような気がする
ただ contrib ライブラリを使っているのでおまけ。? は Groovy 由来だと思うので書いてみた。
なぜメモ化も重要か
1年前ぐらいに読んでよくわからなかったけど、ようやく理解できた気がしたので書いてみる。
John Hughes 氏の主張
プログラムをモジュール化するには関数プログラミングのスタイルで書くといいよ。
- 高階関数を使うと捗る
- 無限を使うと捗る
20年以上前に書かれたものだが今でもこの主張は通るし Groovy でも通る。
高階関数を使う
// 基本的な関数と inject を組み合わせて処理を行う def add(x,y) { x + y } def mul(x,y) { x * y } assert [*1..10].inject(0, this.&add) == 55 assert [*1..10].inject(1, this.&mul) == 3628800 // 組み合わせた処理は新しい処理として定義できる def sum (list) { list.inject(0, this.&add) } def product(list) { list.inject(1, this.&mul) } assert sum (1..10) == 55 assert product(1..10) == 3628800 // Groovy では標準で提供されているものもある assert [*1..10].sum() == 55
データ構造ごとに高階関数を定義すると捗るらしい。
Groovy の Collection には予め高階関数が定義されているので普段から使っている。
Haskell の foldr を理解するときにここの説明がとてもわかりやすかった。
他に Groovy にはない Tree 構造に対する inject の定義も書かれている。
フィボナッチ数列で考える
無限を使う例が個人的に理解の妨げになった。平方根、微分、積分である。
許容誤差の範囲に収まるまでループしながら処理するのだが、無限を使うことより数学に話を持っていかれるのでここではフィボナッチ数列で考える。
100 から 1000 までのフィボナッチ数を表示する
再利用を考えずに書いてみる
def (a,b) = [0,1] while (a < 1000) { if (100 <= a && a < 1000) println a (a,b) = [b,a+b] } // 144 // 233 // 377 // 610 // 987
さらに11番目から20番目までのフィボナッチ数を表示することになると再度フィボナッチ数のループが必要になる。
フィボナッチ数ならまだいいが複雑な処理になるが2つになるとメンテナンスが面倒だ。
そこで考えを変えてフィボナッチ数列を作る部分と数列から条件に当てはめる部分を分けておくと再利用しやすい。
フィボナッチ数列は予めどこまで必要かわかっていないので無限に生成するようにする。
Iterator を使う
遅延評価なら無限に生成するしても問題ないという話なのだが、Groovy では使えないので Iterator を使う。
Iterator は無限に続くが必要な部分だけ取り出せばよい。
def fib() { def (a,b) = [0,1] return new Iterator() { @Override boolean hasNext() { true } @Override def next() { def cur = a (a,b) = [b,a+b] return cur } @Override void remove() { throw new UnsupportedOperationException() } } } // 100から1000までのフィボナッチ数を表示する // dropWhile, takeWhile は Groovy 1.8.7 以降 //println fib().dropWhile{ it < 100 }.takeWhile{ it < 1000 }.collect() // 11番目から20番目までのフィボナッチ数を表示する println fib().drop(10).take(10).collect()
ジェネレータを使う
Python 風のジェネレータを使うとループと同じ形式で記述できて便利だ。
http://groovy.codehaus.org/Roadmap によると Groovy3.0 (バージョンがずれたので旧Groovy2.0) で導入されるらしい。
今回はこのあいだ作ったもので
import static Itertools.gen def fib = gen{ yield -> def (a,b) = [0,1] while (true) { yield(a) (a,b) = [b,a+b] } } // 11番目から20番目までを表示する println fib.iterator().drop(10).take(10).collect()
無限リスト便利だねという話だったのだが無限を扱えるのは無限リストだけなのだろうか？
メモ化で無限を扱う
Groovy には便利なメモ化があるのでこれでも無限を扱える。
関数型の考え方: Groovy に隠された関数型の機能、第 3 回 によるとこれも関数型の機能らしい。
// n 番目のフィボナッチ数を返すクロージャをメモ化しておけば Iterator のように扱える // 全部メモ化するとメモリを喰い過ぎるので3つだけにする(2つだと再帰してしまった) fib = { n -> n <= 1 ? n : fib(n-1) + fib(n-2) }.memoizeAtMost(3) // 100から1000までのフィボナッチ数を表示する for (int i = 0; fib(i) < 1000 ; i++) { if (fib(i) >= 100) println fib(i) } // 11番目から20番目までのフィボナッチ数を表示する for (int i = 10; i < 20; i++) { println fib(i) }
終わりに
Groovy で無限を扱う方法をいくつか書いてみた。
テキストではこの後応用として○×ゲームを作るのだがまだ読んでないのでまた書くかも。
*1:翻訳された山下伸夫氏に感謝
実装時の型と評価後の型
前回の木構造と同じようにリストを表現するとどうなるのか?
def tree = { [:].withDefault{ owner.call() } } def list = { h, t -> [h, { t?.call() }] }
ちょっと意味が違う気がするけど気持ちの問題の範囲なので続ける。
h は先頭の要素で、t は評価すると残りのリストを返し、list は遅延評価されるリストになる。
def ones = list(1){ list(1){ owner.call() } } assert 1 == ones[0] assert 1 == ones[1]()[0] assert 1 == ones[1]()[1]()[0] assert 1 == ones[1]()[1]()[1]()[0] assert 1 == ones[1]()[1]()[1]()[1]()[0]
今回は使う側で{ owner.call() }する。
この例は3回が適切だが中毒性があるので5回書いてしまった。
なので毒を抜く。
def lazySeq(head, generateTail) { def seq = [:] seq.head = { head } seq.tail = { generateTail?.call() } return seq }
コンストラクタとファクトリメソッドの違いはあるが http://groovy.codehaus.org/Functional+Programming+with+Groovy の LazyList の形になった。
あなたは何型ですか？
def twos = lazySeq(2){ lazySeq(2){ owner.call() } } assert 2 == twos.head() assert 2 == twos.tail().head() assert 2 == twos.tail().tail().head() assert 2 == [2,2,2].head() assert 2 == [2,2,2].tail().head() assert 2 == [2,2,2].tail().tail().head()
動的言語では常に型を知る必要はないが、失礼のないように頭の中では知っておくのがマナー。
twos はリストのように扱えるので List にしてしまっていいのだろうか？
head と tail の Pair なのだろうか？
is-implemented-in-terms-of 関係
今回調べてみて知ったのだが親子関係を考えるときに is-a, has-a 以外にも実装としての継承を表わす関係があるようだ。
ただし、Java では実装としての継承を使うと隠す方法がないので通常は has-a の関係で表わす。
実装の関係を表に出して問題となっているのが Groovy の Range である。
Range は List を継承してしまった。
おそらく Iterable の意味で使ったのだろうが Range が実装されたときには Iterable が存在しなかったのだ。
twos で考える。
無限に続くので Iterable として扱ってよいだろう。
だが twos が Pair で Pair が Iterable を継承していたら、2つしかないはずが終わらなくて目撃者は通報するだろう。
Pair を継承したときには Pair は Iterable を継承していなかったというアリバイがあったらどうだろうか？
Pair であることは内緒にして Iterable にする
def lazySeq(head, generateTail) { return new Iterable() { def head() { head } def tail() { generateTail?.call() } @Override Iterator iterator() { def curr = this def value = [] return new Iterator() { @Override boolean hasNext() { if (value.empty && curr) { value.add(curr.head()) curr = curr.tail() } return !value.empty } @Override def next() { value.remove(0) } @Override void remove() { throw new UnsupportedOperationException() } } } } } def integers(n) { return lazySeq(n){ integers(n+1) } } def ints = integers(1) assert 1 == ints.head() assert 2 == ints.tail().head() assert 3 == ints.tail().tail().head() assert [1,2,3] == integers(1).iterator().take(3).collect()
まとめて数えられるようになった。
評価後の型
ここでもう一つの疑問が
integers(1) は List なのだろうか？
List なら比較できるべきなのだろうか？
// == になるようにしますか？ assert integers(1) != integers(1) assert integers(1).iterator() != integers(1).iterator()
ちなみに Haskell ではリストは比較できなければならないので実行してくれるが結果は返さない。
[1..] == [1..] -- Interrupted.
ここで静的な型と実行時の型があるように実は評価後の型と評価前の型があるということにようやく気がついた。
Haskell の型に書かれているのは評価後の型だ。
[1..] 自体は何者かわからない評価されるとリストになる何かだが遅延評価の言語では区別する必要がない。
Groovy は遅延評価の言語ではないので実装すると評価前の型も表にでてきてしまう。
integers(1) は評価すると List をくれる何かであって List でもないし比較もできない。
ファクトリメソッド
最初の tree や list は携帯型のファクトリメソッドともいえる。
クロージャのおかげでファクトリメソッド自体も動けるようになったみたいだ。
そして遅延評価で再帰している。
Groovy 1.8.7 では List#withDefault のようなファクトリメソッドも追加される。
しかし DefaultGroovyMethods にばかり機能が追加されるようになってしまったので実装としての型がないものには機能が追加されない。
実装の型のオブジェクトからではなく評価されたときの型などに静的なファクトリメソッドが追加されるようになればいいのにと思った。
いまさら Range を Iterable にすることができないのなら Iterable.range も存在すればいいだけだから。
{ owner.call() }
Groovy では木構造が次の形で表現できるらしい。
def tree = { [:].withDefault{ owner.call() } } def users = tree() users.harold.username = 'hrldcpr' users.yates.username = 'tim' def json = new groovy.json.JsonBuilder(users).toString() assert json == '{"harold":{"username":"hrldcpr"},"yates":{"username":"tim"}}'
これは harold cooper 氏の Python One Liner を
def tree(): return defaultdict(tree)
Tim Yates 氏が Groovy に翻訳して
def tree tree = { -> return [:].withDefault{ tree() } }
id:kiy0taka 氏が One Liner にリファクタリングされてこの形になったもの。
def tree = { [:].withDefault{ owner.call() } }
リンク
- one-line tree in python · GitHub
- A two-line tree in Groovy · GitHub
- A one-line tree in Groovy · GitHub
木構造を表わせることも面白いのだけど(それは別エントリで書く)
Groovy 的には Closure 内でその Closure 自身を参照する方法の意味もあるので単独のエントリにした。
以前は Closure の this は Closure 自身を指したが、JSRになった時点で this は Java と同じように、その Closure が定義されている Object を指すようになったそうだ。
def script = this ;{-> assert script == thisObject assert script == this }()
その後 this の変わりに Closure 自身を返すプロパティは定義されていない。
というわけで現時点(Groovy 1.8.6)では Closure.this == { owner.call() } というイディオムかなと思った。
Groovy では1つ書き方があれば適切かはともかくいくつか書き方があるわけで思いついたものを書いておく。
// 知らない人でも意味を把握しやすいと思った def tree = { [:].withDefault{ owner.call() } } // owner が自由変数なら owner() と書けるのだが、owner はプロパティで次の意味になるので書けない def tree = { [:].withDefault{ getOwner()() } } // 人によっては好みに合うかも def tree = { [:].withDefault(identity{it}) } def tree = { [:].withDefault(with{it}) } // obj.findAll() == obj def tree = { [:].withDefault(findAll()) } def tree = { [:].withDefault(collect()) } // タイプ数は思いついた中で最小 def tree = { [:].withDefault(grep()) } def tree = { [:].withDefault(find()) } // 1回しか呼ばれない memoize // 他に Closure の中で使われているケースがないか探したが見つからなかった (Github 調べ) def tree = { [:].withDefault(memoize()) } // 見た目はシンプルだが memoize と同じで人を惑わせる力がある def tree = { [:].withDefault(rcurry()) } // 演算子で書ければ... def tree = { [:].withDefault(rightShift{it}) } def tree = { [:].withDefault(leftShift{it}) }
Hamming numbers in SQL
SQL-99 では再帰が使えるので、それを使って Hamming numbers を出力する。
まずは、再帰クエリが使えるデータベースを調べてみる。
H2 Database が一番手軽に導入できるのでこれを使ってみる。
再帰クエリの書き方
H2 Dataabse のドキュメントから再帰クエリの書き方を引用する。
WITH RECURSIVE recursiveQueryName(columnName, ...) AS ( nonRecursiveSelect UNION ALL recursiveSelect ) select
現時点では H2 Database の再帰クエリは experimental support らしい。
試したところ、次の2つのことができなかった。
- UNION ALL の代わりに UNION を使う
- WITH 句で複数のテーブルを宣言する
両方ともあとで PostgreSQL で試す。Hamming numbers を書く上で障害にはならない。
Hamming numbers で WITH RECURSIVE の理解を深める
-- H2 Database Engine version 1.3.165 WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION ALL ( SELECT 2*n FROM hamming WHERE 2*n < 100 UNION SELECT 3*n FROM hamming WHERE 3*n < 100 UNION SELECT 5*n FROM hamming WHERE 5*n < 100 ) ) SELECT n FROM hamming /*GROUP BY n*/ ORDER BY n LIMIT 20 -- 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
H2 Database の再帰クエリでは、recursiveSelect に終了条件を指定しないと無限ループになって返ってこない。
Hamming numbers の最初の20個は100までに現れることは予め知っているのでそれを終了条件に指定した。
突然ですが、ここで問題です。
筆者はコメントアウトしている GROUP BY を必要だと思っていました。
しかし、必要ありませんでした。どうして不要なのでしょうか？
ヒント
不要な理由は2つあって、ひとつは数学的なもので、もうひとつが WITH RECURSIVE によるものである。
今知りたいのは、WITH RECURSIVE なので数学的な理由を説明しておく。
それは、素因数分解の一意性によるものである。*1
2,3,5 の3つの数字から同じ数字を何回選んでもいいので n 個選んで掛け合わせた数字と n+1 個選んで掛け合わせた数字は決して同じにならない。
そして n が違えば掛け合わせた数字は同じにならない。
ノブレス・オブリージュ
ここまで読んだ人は WITH RECURSIVE に関心のある人である。
したがって、次のどちらかの理由で最後まで読むことをお勧めする。
何故 GROUP BY が不要なのかわからない人は、理由を知るために最後まで読んだ方がよい。
理由がわかっている人は、筆者が間違ったことを広めていないか確認するために最後まで読んだ方がよい。
GROUP BY が必要だと思っていた理由
-- H2 Database Engine version 1.3.165 WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION ALL ( SELECT 2*n FROM hamming WHERE 2*n < 100 UNION ALL SELECT 3*n FROM hamming WHERE 3*n < 100 UNION ALL SELECT 5*n FROM hamming WHERE 5*n < 100 ) ) SELECT n FROM hamming /*GROUP BY*/ n ORDER BY n LIMIT 20 -- 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18
recursiveSelect の UNION を UNION ALL に変更しただけだ。
2*n, 3*n, 5*n が重複するのは n が0のときだけのはずなので1以上の場合 UNION でも UNION ALL でも同じはずだ。
UNION と書いてはいたが筆者の想定では UNION ALL の意味で使っており、タイプ数をケチっただけだ。
Hamming numbers in PostgreSQL
H2 Database の WITH RECURSIVE は experimental support だし PostgreSQL なら動作するかもしれない。
調べているとどうやら PostgreSQL では recursiveSelect での終了条件も必須でないし、UNION も使えるらしい。
がしかし...
-- PostgreSQL 9.1.3 -- ERROR: クエリー "hamming" への再帰参照が２回以上現れてはなりません WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION ( SELECT 2*n FROM hamming UNION ALL SELECT 3*n FROM hamming UNION ALL SELECT 5*n FROM hamming ) ) SELECT n FROM hamming ORDER BY LIMIT 20
これで H2 Database と比べることができなくなった。
さらに
-- PostgreSQL 9.1.3 -- ERROR: integerの範囲外です WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION SELECT m*n FROM hamming, factor ), factor(m) AS ( SELECT 2 UNION SELECT 3 UNION SELECT 5 ) SELECT n FROM hamming ORDER BY n LIMIT 20
無限リストは返せるがソートはできないようだ。残念だがこれは想定内。
-- PostgreSQL 9.1.3 WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION SELECT m*n FROM hamming, factor WHERE m*n < 100 ), factor(m) AS ( SELECT 2 UNION SELECT 3 UNION SELECT 5 ) SELECT n FROM hamming n ORDER BY n LIMIT 20 -- 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
ようやく Hamming numbers を手に入れた。
間違ったモデル
DB 間の違いは比較できなくなったので、SQL の結果を再現する手続き型の疑似コード *2 を書いてみる。
def withRecursive(opts=[all:false], nonRecursive, recursive) { def result = [] def queue = [] as Queue for (work in nonRecursive.call()) queue.offer(work) while (queue) { def n = queue.poll() for (work in recursive.call(n)) queue.offer(work) result.add(n) } if (opts.all) return result else return result.unique() }
今まで実行した SQL を疑似コードで実行して確認する。
-- PostgreSQL 9.1.3 WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION SELECT m*n FROM hamming, factor WHERE m*n < 100 ), factor(m) AS ( SELECT 2 UNION SELECT 3 UNION SELECT 5 ) SELECT n FROM hamming n LIMIT 20 -- 1 5 2 3 25 10 15 4 6 9 50 75 20 30 45 8 12 18 27 40
def nonRecursive = { [1] } def recursive = { n -> def temp = [] for (m in [5,2,3]) if (m*n < 100) temp.add(m*n) return temp } println withRecursive(all:false, nonRecursive, recursive).take(20).join(' ') // 1 5 2 3 25 10 15 4 6 9 50 75 20 30 45 8 12 18 27 40
5,2,3 になっているのは UNION の結果の順序に合わせたため。
完全に一致。
-- H2 Database Engine version 1.3.165 WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION ALL ( SELECT 2*n FROM hamming WHERE 2*n < 100 UNION ALL SELECT 3*n FROM hamming WHERE 3*n < 100 UNION ALL SELECT 5*n FROM hamming WHERE 5*n < 100 ) ) SELECT n FROM hamming /*GROUP BY*/ n ORDER BY n LIMIT 20 -- 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18
def nonRecursive = { [1] } def recursive = { n -> def temp = [] for (m in [2,3,5]) if (m*n < 100) temp.add(m*n) return temp } println withRecursive(all:true, nonRecursive, recursive).sort().take(20).join(' ') // 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18
こちらも完全に一致した。
ただしこのモデルでは次の結果を再現することができない。
-- H2 Database Engine version 1.3.165 WITH RECURSIVE hamming(n) AS ( SELECT 1 UNION ALL ( SELECT 2*n FROM hamming WHERE 2*n < 100 UNION SELECT 3*n FROM hamming WHERE 3*n < 100 UNION SELECT 5*n FROM hamming WHERE 5*n < 100 ) ) SELECT n FROM hamming /*GROUP BY n*/ LIMIT 20 -- 1 2 3 5 9 10 25 4 6 15 18 50 20 8 75 27 12 45 30 81
正しいモデル
探したところ PostgreSQL のドキュメントに書かれているようなのでこれを引用する。
再帰的問い合わせの評価
- 非再帰的表現を評価します。 UNION（しかしUNION ALLではありません）では、重複行を廃棄します。その再帰的問い合わせの結果の残っている全ての行を盛り込み、同時にそれらを暫定的作業テーブルに置きます。
- 作業テーブルが空でないのであればこれらの手順を繰り返します。
注意: 厳密には、この手順は反復であって再帰ではありませんが、RECURSIVEはSQL標準化委員会で選ばれた用語です。
高度な日本語が使われているので、理解できるようにこれを表現する手続き型の疑似コードを書いてみる。
def withRecursive(opts=[all:false], nonRecursive, recursive) { def result = [] def work = nonRecursive.call() result += work if (!opts.all) result = result.unique() while (work) { work = recursive.call(work) result += work if (!opts.all) result = result.unique() } return result } def nonRecursive = { [1] } def recursive = { work -> def temp = [] for (n in work) { if (2*n <= 100) temp.add(2*n) if (3*n <= 100) temp.add(3*n) if (5*n <= 100) temp.add(5*n) } return temp.unique() } println withRecursive(all:true, nonRecursive, recursive).take(20).join(' ') // 1 2 3 5 4 6 10 9 15 25 8 12 20 18 30 50 27 45 75 16 println withRecursive(all:true, nonRecursive, recursive).sort().take(20).join(' ') // 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
unique() と UNION の違いか完全に一致しない。
しかしこれが正しいモデルだ。8 は決して 25 より前に現れない。
間違ったモデルで動作していたものも確認する。
def nonRecursive = { [1] } def recursive = { work -> def temp = [] for (n in work) { if (2*n <= 100) temp.add(2*n) if (3*n <= 100) temp.add(3*n) if (5*n <= 100) temp.add(5*n) } return temp } println withRecursive(all:true, nonRecursive, recursive).sort().take(20).join(' ') // 1 2 3 4 5 6 6 8 9 10 10 12 12 12 15 15 16 18 18 18
問題の答え
WITH RECURSIVE の再帰では recursiveSelect に受け渡されるのはレコード単位ではなく1つ前のクエリの結果だから。
2 3 5 ...
ではなく
2,3,5 2*2,...,5*5 2*2*2,...,5*5*5 ...
と渡ってくる。
1つ前の結果が渡ってくるのは SQL 以外と同じだが、日ごろ recursiveSelect で1レコードしか返していないと勘違いしてしまう。
Hamming numbers の recursiveSelect のクエリの結果は素因数の個数が等しい数の集まりである。
したがって、個数が等しいものの中で重複を取り除けば素因数分解の一意性により他の個数との重複は気にしなくてもよい。
よって GROUP BY は不要である。
Qed.
*1:素因数分解の一意性は 素因数分解 - Wikipedia や『数学ガール』 を持っているなら 8.9.3 に載っている
*2:Groovy です
