Hamming number その2
id:akihiro4chawon 氏のエントリの 1つ目の実装を見て Haskell の実装と同じだったので驚いた。
val hamming: Stream[BigInt] = BigInt(1) #:: merge(merge(hamming map {_ * 2}, hamming map {_ * 3}), hamming map {_ * 5}) def merge[T <% Ordered[T]](xs: Stream[T], ys: Stream[T]): Stream[T] = { val (x, y) = (xs.head, ys.head) if (x < y) x #:: merge(xs.tail, ys) else if (x > y) y #:: merge(xs, ys.tail) else x #:: merge(xs.tail, ys.tail) } assert(hamming.take(20) == Stream(1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36))
前回 yield がないと実装できないのかなと思ったのは Scala が 2つとも Haskell と違う実装だったからということも理由にある。一応、Scala の Stream も試してみたがうまくいかなかったからだ。
scala> val xs:Stream[Int] = 1+:xs java.lang.NullPointerException
Java や Groovy は右辺から評価される*1のできっと Scala もそうなのだと考えてしまったことが間違いの始まりだったらしい。そもそも参照できないなら NullPointerException ではないのだろうと今は思うのだがそのときは気づかなかったのだ。*2
scala> val xs:Stream[Int] = 1#::xs xs: Stream[Int] = Stream(1, ?) scala> xs take 3 foreach println 1 1 1
API には見当たらないのだが #:: を使えばできるみたいだ。
昔読んだ小説のメモだが *3
観察に先立って確固とした目標がイメージできなければ人はものをみたことにはならないといっても過言ではない。認識するためには予め用意された仮説が必要なのである。
『今はもうない』 森博嗣
プログラムを書く私には、カエサルの言葉よりしっくりくる。
できないかもと思っていたのでみえていなかったものがあるのだろう。
Scala で実装できるということは Functional Java*4 で実装でき Groovy でも実装できる。
Functional Java の Stream をよく見てみると append には引数が Stream のものと P1 で Wrap されたものがある。
今までは _1 で取り出すのが面倒だなと思っていたが、意味がないのに面倒になっているはずがないのでその当たりを調べながら実装したら動いてしまった。
@Grab('org.functionaljava:fj:3.0') import fj.* import static fj.data.Stream.* import static fj.Equal.intEqual import static fj.Equal.streamEqual import static fj.Show.intShow import static fj.Show.streamShow hamming = cons().f(1).f(({ merge(merge(hamming.map({ it * 2 } as F), hamming.map({ it * 3 } as F)), hamming.map({ it * 5 } as F)) } as F).lazy().f()) merge = { xs, ys -> def (x, y) = [xs.head(), ys.head()] // println ([x,y]) x < y ? cons().f(x).f(({ merge(xs.tail()._1(), ys) } as F).lazy().f()) : x > y ? cons().f(y).f(({ merge(xs, ys.tail()._1()) } as F).lazy().f()) : cons().f(x).f(({ merge(xs.tail()._1(), ys.tail()._1()) } as F).lazy().f()) } // hamming.take(20).foreach(Effect.f({ println it } as F)) println streamShow(intShow).showS(hamming.take(20)) assert streamEqual(intEqual).eq(hamming.take(20), stream(1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36))
P1 はタメになる部分でそのタメは F#lazy で作る。*5 tail が呼び出されると再帰の 1つ前の merge を実行する。*6
id:amachang 氏の Haskell のリストと遅延評価が少し分かった - IT戦記 を読んで似たようなことを試してはいたのだが評価する位置を間違えて無限ループさせていた。
Functional Java を参考に Groovy に書き直してみる。
class Stream { def head, tail_ static def cons(head, tail_) { new Stream(head: head, tail_: tail_) } static def cons_(head, gen) { cons(head){ cons_(gen(head), gen) } } def getTail() { tail_() } def map(f) { cons(f(head)){ this.tail.map(f) } } def merge(ys) { def (x, y) = [head, ys.head] x < y ? cons(x){ this.tail.merge(ys) } : x > y ? cons(y){ this.merge(ys.tail) } : cons(x){ this.tail.merge(ys.tail) } } def take(n) { def rs = [] def xs = this n.times { rs << xs.head xs = xs.tail } rs } def getAt(n) { def xs = this for (def i = 0; i < n - 1; i++) { xs = xs.tail } xs.head } @Override String toString() { "Stream($head, ?)" } } assert Stream.cons_(1){ it + 1 }.take(3) == [1,2,3] assert Stream.cons_(1){ it + 1 }.map { it * 2 }.take(3) == [2,4,6] def odds = Stream.cons_(1){ it + 2 } def evens = Stream.cons_(2){ it + 2 } assert odds.merge(evens).take(3) == [1,2,3] hamming = Stream.cons(1){ hamming.map{ 2 * it }.merge(hamming.map{ 3 * it }).merge(hamming.map{ 5 * it }) } assert hamming.take(20) == [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
この実装では参照をつかんだままになるようで他のテストはメモリが足りなくて実行できない*7のだが最初の 20 個は取得できた。
遅延評価のメモリの話は裏を返せば Queue として使えるということみたいだ。
実装できたのは id:akihiro4chawon 氏と Functional Java のおかげである。感謝。
