最長重複文字列問題 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 かは最近知った。
