Journal InTime

_ [Ruby] 関西オープンソース2004(一日目)

というわけで、行って来た。

スーパークリエータならぬスーパーデストロイヤーの雄也君の運転で 大阪へ移動。何度か悲鳴をあげたけど何とか無事についた。彼の車の 保険は家族限定なので運転を代われないのだ(大人は「事故ったらすぐに 席を代わればいいですよ」なんて言ってはいけない)。

到着がずいぶん遅くなってしまったので、新部さんのセッションと、宮原 さんのセッションしか見られなかった。新部さんの「コードの批評という分野 を確立したい」というお話には大変感銘を受けたが、文学のように批評する側と される側が不幸な関係にならないといいですね。 まあ、コードの場合は批評するだけで自分では書かないという人はあまり 出て来ないと思うけど。

夜は懇親会も気になったけど、財布と相談して、うささんに鰻をたかる会の方に参加。メニューに白焼があったので今日こそ食べられるかと思ったが、 残念ながら来月からだった。

_ flat_map、非決定性計算、リスト内包表記

Ruby 1.9では、Enumerable#flat_mapというメソッドが追加されている。

%w(ruby perl python).flat_map {|i| i.chars.to_a}
#=> ["r", "u", "b", "y", "p", "e", "r", "l", "p", "y", "t", "h", "o", "n"]

といった動作をするもので、要はブロックが返す配列を連結した配列を返す。

%w(ruby perl python).map {|i| i.chars.to_a}.flatten(1)

とすれば同じことができるのにどうしてわざわざ追加したのか疑問に思われるかもしれないが、 実はflat_mapが追加されたということは、Rubyの配列がHaskellのリストモナドのように使えることを意味している。

以前の日記で非決定性計算について書いたが、 Ruby 1.9では継続が拡張ライブラリに格下げになっているので、代りにflat_mapで書いてみよう。

p (1..5).flat_map {|baker|
    (1..5).flat_map {|cooper|
      (1..5).flat_map {|fletcher|
        (1..5).flat_map {|miller|
          (1..5).select {|smith|
            [baker, cooper, fletcher, miller, smith].uniq.length == 5 &&
              baker != 5 &&
              cooper != 1 &&
              fletcher != 1 && fletcher != 5 &&
              miller > cooper &&
              (smith - fletcher).abs != 1 &&
              (fletcher - cooper).abs != 1
          }.map {|smith|
            [baker, cooper, fletcher, miller, smith]
          }
        }
      }
    }
  }

確かに計算できる。でもこれってただの全探索なんじゃ…と疑問に思われる方もいるかもしれない。そのとおり。

以前の日記でHaskell版のポイントは遅延評価にあると書いた。上の例は有限集合を扱っているので全探索でもいいわけだが、無限集合を相手にするとそうはいかない。例えば以下のように、x**2 + y**2 == z**2を満たすような整数x,y,zを求めるプログラムを書いたとする。

def pythagorean_triples
  (1..Float::INFINITY).flat_map {|z|
    (1..z).flat_map {|x|
      (x..z).select {|y|
        x**2 + y**2 == z**2
      }.map {|y|
        [x, y, z]
      }
    }
  }
end
p pythagorean_triples.take(10)

このプログラムを実行すると、返って来ない。flat_mapが無限に長い配列を生成しようとしてしまうからだ。 そこで、yhara先生が提案しているEnumerable#lazyを使ってみる。

require_relative "lazy"

def pythagorean_triples
  (1..Float::INFINITY).lazy.flat_map {|z|
    (1..z).lazy.flat_map {|x|
      (x..z).lazy.select {|y|
        x**2 + y**2 == z**2
      }.map {|y|
        [x, y, z]
      }
    }
  }
end
p pythagorean_triples.take(10)

今度はちゃんと以下のような解が得られる。

[[3, 4, 5], [6, 8, 10], [5, 12, 13], [9, 12, 15], [8, 15, 17], [12, 16, 20], [7, 24, 25], [15, 20, 25], [10, 24, 26], [20, 21, 29]]

ちなみにHaskellではリスト内包表記を使ってもっとかっこよく書けるが、意味的には上記のコードと同じだ。

pythags = [ (x, y, z) | z <- [1..], x <- [1..z], y <- [x..z], x^2 + y^2 == z^2 ]

Haskellに比べるとちょっと冗長だが、Scalaでは以下のように書ける。

import scala.math.pow

def from(i: Int): Stream[Int] =
  Stream.cons(i, from(i + 1))

def pythagoreanTriples(): Stream[(Int, Int, Int)] =
  for (z <- from(1);
       x <- 1 to z;
       y <- x to z;
       if pow(x, 2) + pow(y, 2) == pow(z, 2))
    yield (x, y, z)

for (i <- pythagoreanTriples().take(10))
  println(i)

実は、Scalaのfor式はリスト内包表記と同等で、

for (z <- from(1);
     x <- 1 to z;
     y <- x to z;
     if pow(x, 2) + pow(y, 2) == pow(z, 2))
  yield (x, y, z)

は

from(1).flatMap(z => 
  (1 to z).flatMap(x =>
    (x to z).withFilter(y =>
      pow(x, 2) + pow(y, 2) == pow(z, 2)).map(y =>
        (x, y, z))))

のような形に変換される。 Ruby版とHaskell版、Scala版は、見た目が違うだけで意味的にはほとんど同じ。

Rubyのfor式も

for (z in 1..Float::INFINITY;
     x in 1..z;
     y in x..z;
     if x**2 + y**2 == z**2)
  [x, y, z]
end

と書けるように拡張したら面白いかもしれない。

ただ、Scalaではyieldの有無でflatMap/mapかforeachかを切り替えているようだが、Rubyの場合yieldは他の意味に使っているので、もうちょっと工夫が必要そう。

x = for (...) do ... end

のように値が要求される場合はflat_map/mapを使って、

for (...) do ... end

のように使ってないように見える場合はeachを使う、というのを考えたが、

def foo
  for (...) do ... end
end

だと値がほしいのかどうか曖昧なので

def foo
  return for (...) do ... end
end

のようにreturnを書かないといけなくなるのがちょっと気持ち悪い。

ここで静的型があればfooの戻り値の型から判断できるのに…とか思ってしまったら(Ruby的には)負け。