Journal InTime

_ 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的には)負け。