RubyのArray#flat_mapの勉強

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

## flat_mapでFizzBuzzしてみる

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

```Ruby
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にくるむ。

```Ruby
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というものが書ける。

```Ruby
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

```Ruby
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モナドについて、だいたい[ここらへん](http://d.hatena.ne.jp/papamitra/20101002/scala_monad)とか[ここらへん](http://www.sampou.org/haskell/a-a-monads/html/listmonad.html)を参考にしてます。）

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

```Ruby
## 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に当てはまるかどうか。

```Ruby
## 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`は非決定的値を一つの値にくっつける操作を表すらしい。

らしいばっかりでは全く分からないので、実際に計算をさせてみる。
実例として、ピタゴラス数、a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup> を満たす互いに素な３つの数の組を求める。

```Ruby
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構文みたいな構文糖衣がないので難しいかな、と思っていたら、[このへん](http://yuroyoro.hatenablog.com/entry/2012/08/17/201443)を見ると一番内側の関数をcurry化すればフラットなメソッドチェーンに置き換えられるらしい。

```Ruby
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`が入り乱れてなにやら読みにくい状況になってしまっている。
もう一工夫、うまくパターン化してなんとかすっきりさせられないだろうか。

[さっきのここ](http://yuroyoro.hatenablog.com/entry/2012/08/17/201443)にある、「Applicativeっぽいなにか」と「lift」を定義する。`applicate`は`map`のままでは動かなくて`flat_map`にしないといけないのだが、なぜそうなのかという肝心のところは分かってない。

```Ruby
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つの引数を配列のまま渡している、という感じなのだろうか。