LoginSignup
11

More than 3 years have passed since last update.

RubyのArray#flat_mapの勉強

Last updated at Posted at 2014-07-19
  • (update 2014-7-22) 「非決定性計算」について調べたので定義について加筆した
  • (update 2019-5-24) flat_mapで要素を増やすことができる例を追記した

flat_mapでFizzBuzzしてみる

flat_mapの難しい側面に触れる前に、とりあえずお気楽な例としてFizzBuzzを取り上げる。
まずは普通のmap

fizzbuzz = ->(i){ i % 3 == 0 && i % 5 == 0 ? 'FizzBuzz' : i }
fizz = ->(i){ i % 3 == 0 ? 'Fizz' : i }
buzz = ->(i){ i % 5 == 0 ? 'Buzz' : i }
(1..16).map(&fizzbuzz).map(&fizz).map(&buzz)
# => [1, 2, "Fizz", 4, "Buzz", "Fizz", 7, 8, "Fizz", "Buzz", 11, "Fizz", 13, 14, "FizzBuzz", 16]

これでちゃんと動くのはひとつズルしていて、String#%が文字列を返すという特性を利用している。
これをflat_mapにするには各々の関数で返り値をArrayにくるむ。

fizz = ->(i){ i % 3 == 0 ? ['Fizz'] : [i] }
buzz = ->(i){ i % 5 == 0 ? ['Buzz'] : [i] }
fizzbuzz = ->(i){ i % 3 == 0 && i % 5 == 0 ? ['FizzBuzz'] : [i] }
(1..16).flat_map(&fizzbuzz).flat_map(&fizz).flat_map(&buzz)
# => [1, 2, "Fizz", 4, "Buzz", "Fizz", 7, 8, "Fizz", "Buzz", 11, "Fizz", 13, 14, "FizzBuzz", 16]

これだけだとmapに比べてなにが嬉しいのかさっぱりだ。だがmapにはないflat_mapの特徴として、空の配列[]を返すと無視してくれるという性質がある。だからselectみたいに特定の数字のときは黙ってしまうFizzBuzzというものが書ける。

silence = ->(i){ i % 4 == 0 ? [] : [i] }
(1..16).flat_map(&fizzbuzz).flat_map(&fizz).flat_map(&buzz).flat_map(&silence)
# => [1, 2, "Fizz", "Buzz", "Fizz", 7, "Fizz", "Buzz", 11, "Fizz", 13, 14, "FizzBuzz"]

逆に、複数の値を入れた配列を返すと、要素数を増やすこともできる。
これは偶数のあとにでたらめな数字を勝手に言うFizzBuzz

random = ->(i){ i % 2 == 0 ? [i, rand(9) + 1] : [i] }
p (1..16).flat_map(&fizzbuzz).flat_map(&fizz).flat_map(&buzz).flat_map(&random)
[1, 2, 7, "Fizz", 4, 3, "Buzz", "Fizz", 7, 8, 7, "Fizz", "Buzz", 11, "Fizz", 13, 14, 1, "FizzBuzz", 16, 3]

つまり、mapは受け取ったリストの中身を加工することしかできないが、flat_mapはそれに加えて要素を増やしたり減らしたりすることもできることが分かる。

RubyのArrayはListモナド?

RubyのArrayflat_mapを使うとListモナドと看做せるらしい。
(Listモナドについて、だいたいここらへんとかここらへんを参考にしてます。)

3つのモナド則を満たすかどうか。

## Arrayにおいて
##  bind(>>=) は flat_map
##  return は [_]

# 1. (return x) >>= f == f x
f = ->(x){ [x + 1] }
[1].flat_map(&f) == f.call(1)  # => true

# 2. m >>= return == m
[1].flat_map{|x| [x] } == [1]  # => true

# 3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)
g = ->(x){ [x * 3] }
[1].flat_map(&f).flat_map(&g)  # => [6]
[1].flat_map {|x| f.call(x).flat_map(&g) }  # => [6]

次にMonadPlusに当てはまるかどうか。

## Arrayにおけるmzeroは[]
mzero = []
m = [1]

# 1. mzero >>= f == mzero
mzero.flat_map(&f)  # => []

# 2. m >>= (\x -> mzero) == mzero
m.flat_map{|x| mzero }  # => []

## Arrayにおけるmplusは(+)
# 3. mzero `mplus` m == m
mzero + a  # => [1]

# 4. m `mplus` mzero == m
a + mzero  # => [1]

以上から、Arrayは、Listモナドの性質を満たしていると言えるっぽい。

非決定性計算 is 何

Listモナドはただのコンテナじゃなくて、非決定性計算を表現できるらしい。
非決定性計算というのは、例えば 5 のような一つの値を「結果が確定した値」、[8, 9, 3] のよう値のリストを「複数の候補値を同時に重ね合わせたような一つの値」とみなす考え方のことらしい。
このような観点では、mzeroが候補がひとつもない失敗した非決定性計算を表し、mplusは非決定的値を一つの値にくっつける操作を表すらしい。

らしいばっかりでは全く分からないので、実際に計算をさせてみる。
実例として、ピタゴラス数、a2 + b2 = c2 を満たす互いに素な3つの数の組を求める。

cp = ->(a,b,c){ a.gcd(b)==1 && b.gcd(c)==1 && a.gcd(c)==1 }
(1..20).flat_map {|a|
 (1..20).flat_map {|b|
  (1..20).flat_map {|c|
    a<b && b<c && a*a+b*b==c*c && cp[a,b,c] ? [[a,b,c]] : []
   }
  }
} # => [[3, 4, 5], [5, 12, 13], [8, 15, 17]]

Rubyにはタプルがないのでちょっと紛らわしいが、[[a,b,c]] はリストにくるまれたタプルくらいの意味で使っている。
それにしても上の例に出てきてしまうflat_mapの入れ子が忌々しいのでなんとかしたい。
Rubyにはdo構文とかfor構文みたいな構文糖衣がないので難しいかな、と思っていたら、このへんを見ると一番内側の関数をcurry化すればフラットなメソッドチェーンに置き換えられるらしい。

arr = 1..20
cp = ->(a,b,c){ a.gcd(b)==1 && b.gcd(c)==1 && a.gcd(c)==1 }
cf = ->(a,b,c){ a<b && b<c && a*a+b*b==c*c && cp[a,b,c] ? [[a,b,c]] : [] }.curry
arr.map(&cf).flat_map{|f| arr.map(&f) }.flat_map{|f| arr.flat_map(&f) }
# => [[3, 4, 5], [5, 12, 13], [8, 15, 17]]

んー。入れ子は消えたけれどもmapflat_mapが入り乱れてなにやら読みにくい状況になってしまっている。
もう一工夫、うまくパターン化してなんとかすっきりさせられないだろうか。

さっきのここにある、「Applicativeっぽいなにか」と「lift」を定義する。applicatemapのままでは動かなくてflat_mapにしないといけないのだが、なぜそうなのかという肝心のところは分かってない。

class Array
  def applicate(functors)
    self.flat_map{|f| functors.flat_map(&f) }
  end
end

class Proc
  def lift(functors)
    functors.map(&self)
  end
end

cf.lift(arr).applicate(arr).applicate(arr)
# => [[3, 4, 5], [5, 12, 13], [8, 15, 17]]

かなりすっきりした。
3引数関数を配列の文脈に引き上げて、3つの引数を配列のまま渡している、という感じなのだろうか。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11