G*アドベントカレンダー2013第23日目の記事です。
大域AST変換と拡張メソッドを使って、Groovyでリスト内包表記を使えるようにしてみます。
リスト内包表記(list comprehension)というのは、HaskellとかScalaとかPythonにも似たものがある便利な言語機能であり、宣言的にリストを構築するためのものです。通常、ループを回したり、あるいはcollect()やfindAll()などの一連の関数呼び出しで作るところを、要素が満たすべき条件を与えることでリストが構築されます。
変数が1つの単純な例
以下、サンプルコードです。
import groovyx.comprehension.keyword.select;
def list = select(n) { n:1..10 }
assert list == [1,2,3,4,5,6,7,8,9,10]
(1)のようにクラスgroovyx.comprehension.keyword.selectを明示的にimportすることで(2)の内包表記構文が使用できるようになります*1。
なお、
import groovyx.comprehension.keyword.select as foreach;
def list = foreach(n) { n:1..10 }
のようにimport asを使ってリネームすることで、内包表記を指定するキーワードをselect以外の別のもの(上ではforeach)に変更することもできます。
利用設定
Gradleでの使用方法
内包表記を利用するための拡張モジュールのバイナリjarを、githubのgh-pagesリポジトリにmavenリポジトリの形でアップロードしてあるので、Gradleから使用するにはbuild.gradleで例えば
gradle 1.7 or later:
apply plugin: 'groovy'
repositories {
jcenter()
}
dependencies {
groovy 'org.codehaus.groovy:groovy-all:2.2.1'
compile 'org.jggug.kobo:groovy-comprehension:0.3'
testCompile 'junit:junit:4.11'
}
のように指定します。
Gradle 1.7 以前のバージョンでは上記repositriesのところを以下のようにします。
repositories {
maven {
url "http://jcenter.bintray.com/"
}
}
(上記は2014.4修正。JCenterに登録したため)
Jarを手動で取得する方法
こちらから直接groovy-comprehension/0.3/groovy-comprehension-0.3.jarを取ってきて、CLASSPATHの通っているところ、例えば~/.groovy/libなどに置くか-cpオプションなどで指定してください。
Grape/@Grabによる使用
以下のようにGrapeの@Grabアノテーションを指定します。
@GrabResolver(name="maven-repo", root="https://raw.github.com/uehaj/maven-repo/gh-pages/snapshot")
@Grab("org.jggug.kobo:groovy-comprehension:0.3")(JCenterに登録したのでGrabResolver指定は不要になりました)
@Grab("org.jggug.kobo:groovy-comprehension:0.3")
import groovyx.comprehension.keyword.select
以下で指摘したgroovyのバグは修正されましたので今は問題なく使用できます。(GROOVY-6446,GROOVY-6447)
注意!
現在のGroovyのバージョン2.2.1において、Grape/@Grabで拡張メソッドを使用すると、JDK7では、不定のタイミングで無効になるときがある(メソッドが拡張されない)という現象に遭遇してしまいました*2。さらにJDK8 eaでは拡張メソッドは常に無効となってしまいます。拡張モジュールの拡張メソッドがgrapeからそもそも使用可能なのかは明確ではないのですが。バグ報告チケットは切っておきましたGROOVY-6446,GROOVY-6447が将来修正されるかどうかは不明です。
拡張メソッドが有効になっていないと以下のような例外が発生します。
Caught: groovy.lang.MissingMethodException: No signature of method: groovy.lang.IntRange.bind() is applicable for argument types: (sample1_2$_run_closure1) values: [sample1_2$_run_closure1@5587f3a]
:もし、このような問題が発生するなら、gradleやmavenを使用するか直接jarを使用してください。
|
文法解説
先の例の
def list = select(n) { n:1..10 }
の(A)が内包表記の使用です。意味は、1から10の範囲のnを取ってくる、ということです。つまりこの場合(A)は
list = 1..10
と同じ意味です。なお、(A)は
def list = select { n:1..10; yield(n) }
と書くこともでき、意味は等価です。
制約条件(Guard)を付ける
「nが偶数」という条件を以下のように追加することもできます。
def list = select(n) { n:1..10; n%2 == 0 }
assert list == [2,4,6,8,10]
「n:1..10」の次に、nが満すべき条件式「n%2 == 0」をガードとして列挙します。
上記は
def list = select(n) { n:1..10; guard(n%2 == 0) }
assert list == [2,4,6,8,10]
と書くこともできます。guard指定しようとする式が、実行時にboolean型の値を返すなら、guardを省略することができるということです。この機能をAuto Guardと呼んでいます(オリジナルの工夫)。
複数の条件を指定することもできます。
def list = select(n) { n:1..10; n%2 == 0; n%3 ==0 }
assert list == [6]
上記は「n%2 == 0 && n%3 ==0」のように&&で繋げたのと同じ意味です。
変数が2つの例
複数の変数を指定できます。以下では、nに加え、変数mの指定を範囲'A'..'B'で追加しています。
def list = select(n+m) { n:1..10; m:'A'..'B' }
assert list == ['1A', '1B', '2A', '2B', '3A', '3B', '4A', '4B', '5A','5B',
'6A', '6B', '7A', '7B', '8A', '8B', '9A', '9B', '10A', '10B']
この場合、変数nとmのすべての組み合わせに対してn+mを計算したものをリストとして得ることができます。上記は以下と等価です。
def list = []
for (n in 1..10) {
for (m in 'A'..'B') {
list += (n+m)
}
}
assert list == ['1A', '1B', '2A', '2B', '3A', '3B', '4A', '4B', '5A','5B',
'6A', '6B', '7A', '7B', '8A', '8B', '9A', '9B', '10A', '10B']
変数2つに制約条件を組合せる
以下のようにさらに制約条件を付けることもできます。
def list = select(n+m) {
n: 1..10
n%2 == 0
m: 'A'..'B'
}
assert list == ['2A', '2B', '4A', '4B', '6A', '6B', '8A', '8B', '10A', '10B']
ちょっと応用的な例として、方程式「a ^ 2 + b ^ 2 == c ^ 2」を満たす数の組(ピタゴラス数)を求めてみます。cを長辺、a,bを他の辺とする直角二等辺三角形の辺の長さの間の関係です。aが1..10の範囲のときに限定すると、
def list = select("(a=$a,b=$b,c=$c)") {
a: 1..10
b: 1..a
c: a..a+b
a**2 + b**2 == c**2
}
assert list == ["(a=4,b=3,c=5)", "(a=8,b=6,c=10)"]
Java8のストリームでピタゴラス数を求める
いままでは、リストに対する内包表記でした。Java8のストリーム
(java.util.stream.Stream)を内包表記で使用することも可能です。
import static java.util.stream.Stream.*
:
def answer = select ([a,b,c]) {
a: iterate(1,{it+1})
b: iterate(1,{it+1}).limit(a-1)
c: iterate(a,{it+1}).limit(b)
a**2 + b**2 == c**2
}.skip(100).findFirst().get()
assert answer == [144, 108, 180]
上では無限ストリームを生成した上で101番目の解を表示しています。
なお、Streamに対する拡張メソッドは、Java 8用のjar中にのみ含められているので、Gradleとかで指定する場合は
dependencies {
:
compile 'org.jggug.kobo:groovy-comprehension:0.3:java8'
のようにclassifierに「java8」を指定して取得してください。直接取得する場合はこちらにある「groovy-comprehension-0.3-java8.jar」を使用してください。
覆面算を解く
もう一つ応用例です。以下のような覆面算を解いてみます。
SEND
+) MORE
~~~~~~~~~~
MONEY
リスト内包表記を使用して上記を解くコードは以下のとおり。
import groovyx.comprehension.keyword.select;
def digits = 0..9
select("""\
$S$E$N$D
+)$M$O$R$E
$M$O$N$E$Y
""") {
S:digits-0
M:digits-S-0
E:digits-S-M
O:digits-S-M-E
N:digits-S-M-E-O
R:digits-S-M-E-O-N
D:digits-S-M-E-O-N-R
Y:digits-S-M-E-O-N-R-D
(S*1000+E*100+N*10+D) + (M*1000+O*100+R*10+E) == (M*10000+O*1000+N*100+E*10+Y)
}.each { println it }
S、Mなどの変数ごとの値の範囲と、解が満す条件をガードで与えるだけで、以下のように解が出力されます。
9567
+)1085
10652
仕組み
この内包表記では、リストだけではなく、以下の条件を満たすデータ型が使用できます。
- bindメソッドが定義されている
- yieldメソッドが定義されている(=return, unit)
- autoGuardメソッドが定義されている
以下のコード
def list = select("(a=$a,b=$b,c=$c)") {
a: 1..10
b: 1..a
c: a..a+b
a**2 + b**2 == c**2
}
assert list == ["(a=4,b=3,c=5)", "(a=8,b=6,c=10)"]
がAST変換によって変換された変換後のコードは以下のような感じです。
public java.lang.Object run() {
java.lang.Object list = (1..10).bind({ java.lang.Object a ->
delegate.autoGuard((1.. a )).bind({ java.lang.Object b ->
delegate.autoGuard(( a .. a + b )).bind({ java.lang.Object c ->
delegate.autoGuard( a ** 2 + b ** 2 == c ** 2).bind({ java.lang.Object $$0 ->
delegate.yield("(a=$a,b=$b,c=$c)")
})
})
})
})
list == ['(a=4,b=3,c=5)', '(a=8,b=6,c=10)']
this.println(list)
} bind, autoGuardなどのメソッドがGroovy拡張モジュールのメソッド拡張機構によってjava.util.Listに注入されているので上記が動作します。
メソッドの有無が問題であり、継承は不要です。しかし利便のため、MonadPlusクラスも準備されています。こちらには標準的なguard,autoGuardメソッドが定義されているので、これを継承する場合、以下3つの抽象メソッドを再定義するだけで内包表記に使えるようになります。
これを見るとご存知の方はわかるように、これはモナドの定義です。
実際には、LinqやScalaのそれと同じように、「モナド内包表記」なのです。
Maybeモナドの例
モナドの例として、Maybeを定義してみます。Maybeの定義を含む全体はこちらから。
以下はMaybeを使用している部分の抜粋です。
import groovyx.comprehension.keyword.select;
import groovyx.comprehension.monad.MonadPlus
@Newify([Just,Nothing])
class MaybeMonadTest extends GroovyTestCase {
void test01() {
assert (select {
Just(1)
Just(3)
Nothing()
Just(7)
}) == Nothing()
}
void test02() {
assert (select {
Just(1)
Just(3)
Just(4)
Just(7)
}) == Just(7)
}
void test03() {
assert (((Just(1) >> Just(3)) >> Nothing()) >> Just(7)) == Nothing()
}
}
まあ、Maybeに関しては内包表記で簡潔になるわけではないですね。上記のtest03()のようにbindで繋いだ方がよほどましです(Maybeでは演算子>>>(rightShiftUnsigned)をbind(Haskellの>>=),>>(rightShift)を引数を束縛させないbind(haskellの>>)の意味で定義しています)。
Java8 Optionalについてはまた今度別の記事で書きます。
これは内包表記なのか？
Haskellとの対応で言うと上記はdo構文に対応するわけで、内包表記と呼ぶべきではないのかもしれません。しかしながら、autoGuardで簡潔だし、select (式) { ... }のように先行的にyield(return)式を指定する形式があるので内包表記と呼ぼう、ということです。そうだそうしよう。Scalaのfor「内包表記」の例もあることだし。
ちなみにGroovyにおける同種のものとしては、monadologieの表記や、functional javaを元にしたfunctional groovyなどがあります。他を良く知っているわけではないのですが、今回実装したものの特徴は以下です。
- 表記が簡潔(AST変換で実装するものとしては、私としては限界…)
- autoGuard
- java8 Stream対応
制限と将来
IteratorとかSetに対応してませんがそのうち対応させたいと思います。
モナド(カテゴリ)ライブラリにするつもりはありません。Maybeはおまけです。LinqみたいにDBアクセスに対応させる気もありません。Groovy SQLがあるし。
Parsecみたいなパーサコンビネータを作るのが目標ではあるのですが、表記的にどうすべきか困っているところでもあります。
