- (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のArrayはflat_mapを使うとListモナドと看做せるらしい。
（Listモナドについて、だいたいここらへんとかここらへんを参考にしてます。）
３つのモナド則を満たすかどうか。
## 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 を満たす互いに素な３つの数の組を求める。
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]]
んー。入れ子は消えたけれどもmapとflat_mapが入り乱れてなにやら読みにくい状況になってしまっている。
もう一工夫、うまくパターン化してなんとかすっきりさせられないだろうか。
さっきのここにある、「Applicativeっぽいなにか」と「lift」を定義する。applicateはmapのままでは動かなくて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つの引数を配列のまま渡している、という感じなのだろうか。