複数の Enumerable なオブジェクトで tally したい【追記あり】

# やりたいこと

`Enumerable#tally` はレシーバの要素を `==` で比較して、同じものが何個ずつ含まれているのかを調べ、その結果を Hash オブジェクトで返してくれます。

やりたいのは、例えば、複数の配列を通じて、同じ要素が何個ずつあるか数えたいということです。今回は、次のような ary の例で考えてみます。

```ruby
ary = Array.new(200) do
  Array.new(20) { rand(1..5) }
end
```

# 素朴だが効率の良くない方法
#### その１ ー `tally` で計算した結果をマージする

```ruby
ary.map(&:tally).then do |hashes|
  {}.merge!(*hashes) { |_key, old, new| old + new }
end
=> {1=>759, 3=>801, 4=>833, 2=>851, 5=>756}
```

素朴で単純な方法ですが、Hash オブジェクトを200個も作った上で、それらをマージしなければならず、無駄です。

#### その２ ー ary を平坦化して `tally` する

単純に考えて、二重配列を平坦化すれば、一つのレシーバになるので、これに `tally` すれば上手くいくはずです。

```ruby
ary.flatten.tally   => {1=>759, 3=>801, 4=>833, 2=>851, 5=>756}
```

こんなふうにちゃんと計算できました。しかし、巨大な配列をわざわざ作るのは無駄で、美しくありません。

当然のことながら、Hash オブジェクトを使い回して、累積した計算結果が求められたら、巨大な配列を作る必要はありません。こんな感じです。

```ruby
counter = Hash.new(0)
ary.each { |enum| enum.each { |e| counter[e] += 1 } }
counter
```

これを、Ｃで書かれた `tally` で実現できれば最強・最速なはずです。

# 結果を使い回せる `tally` を考えてみる。

Ruby で書くと、こんな感じです。

```ruby
module Enumerable
  def tally(counter = {})
    each { |e| counter[e] = counter.fetch(e, 0) + 1 }
    counter
  end
end
```

Paul Graham の arc（ダウンロードは[ここ](http://www.arclanguage.org/arc3.2.tar)）を参考にしています。arc では、次のような `counts` 関数が定義されています。

```
(def counts (seq (o c (table)))
  (if (no seq)
      c
      (do (++ (c (car seq) 0))
          (counts (cdr seq) c))))

(let tbl (table)
  (counts '(1 2) tbl)
  (counts '(1 3) tbl))   => #hash((1 . 2) (2 . 1) (3 . 1))
```

計算結果が使い回せていますね。ちなみに、`(o c (table))` の `o` は 仮引数 `c` が optional であり、`(table)` を評価して作られる hash がその初期値になることを意味します。

これを Ruby で再現すると、

```ruby
def counts(ary, counter = {})
  if ary.empty?
    counter
  else
    e, *rest = ary
    counter[e] = counter.fetch(e, 0) + 1
    counts(rest, counter)
end
```

となります。より Ruby 的にすると、

```ruby
def counts(ary, counter = {})
  ary.each do |e|
    counter[e] = counter.fetch(e, 0) + 1
  end
  counter
end
```

となって、ここから先ほど書いた、あったら良いなという `tally` につながっていきます。この `tally` があれば、

```ruby
counter = {}
ary.each { |enum| enum.tally(counter) }
counter       => {1=>759, 3=>801, 4=>833, 2=>851, 5=>756}
```

と書けます。Ｃで実装されていれば、速いはずです。さらに、

```ruby
ary.each_with_object({}) { |enum, counter| enum.tally(counter) }
```

とか

```ruby
ary.each_with_object({}, &:tally)
```

と書けます。（最後の例では、ブロック・パラメータの順序の関係で、`reduce` はできません。）

どうして Ruby は計算結果を使い回そうとしなかったのだろう。

# 現実に戻って、`Enumerable#chain` を使う

`Array#flatten` で巨大な配列を作るのはバカらしいけど、`chain` で Enumerator オブジェクトを一つ作るだけであれば、はるかにスマートです。ただ、`chain` を使うには、レシーバとなる Enumerable なオブジェクトが必要になります。そこで、やむなく、

```ruby
ary[0].chain(*ary[1..]).tally
```

とすることになりますが、少し不格好です。更にやむなく、多重代入を使うことにします。

```ruby
enum, *rest = ary
enum.chain(*rest).tally
```

スッキリ書けましたが、`enum` や `rest` で名前空間を汚したくありませんよね。そこで、

```ruby
ary.then { |enum, *rest| enum.chain(*rest).tally }
```

のようにするとＯＫです。

ただ、ary をわざわざ分割するのはバカらしいことです。だって、ruby の[内部](https://github.com/ruby/ruby/blob/bfe706716f7692f0a672a15a261ffffa25526cb1/enumerator.c#L3277)では、`rb_ary_cat` を使って、`enum` と `rest` をもう一度一つの配列につなぎ合わせて処理をしているからです。

それなら、いっそのこと、

```ruby
[].chain(*ary).tally
```

にすればどうか。何と、一番スッキリした感じになりました。

「これで決まり！」と言いたいところですが、無駄に空の配列を chain しているのが気になります。
`Kernel#chain(*enums)` があれば、スッキリするな〜。

```ruby
chain(*ary).tally
```

# 結論

`Enumerable#tally(counter = {})` や `Kernel#chain(*enums)` を実装してほしい。

どなたか、もっとスマートな方法があれば、お教えください。

# 追記１

コメント欄で @obelisk68 さんとやり取りをしていて分かったことですが、`Kernel#chain(*enums)` だと、配列の要素をわざわざスタックに展開するという無駄な処理をすることになるので、`Kernel#.chain(enums)` の方が使い勝手がいいかもしれません。

全体が一つの配列になっていないのであれば、単純に `Enumerable#chain(*enums)` を使えば良いわけですから。

ただ、いろいろ考えると、Enumerator オブジェクトを作るのだから、`Enumerator.product` にならって

```ruby
class Enumerator
  def self.chain(enums)
    Enumerator.new do |y|
      enums.each {|enum| enum.each(&y) }
    end
  end
end
```

が良いのかな？ これがあると、

```ruby
Enumerator.chain(ary).tally
```

# 追記２

これも @obelisk68 さんに教えてもらった、`ary.lazy.flat_map ...` の件です。

整合性とか考えていませんが、lazy なオブジェクトを返す `Enumerator::Lazy.flatten` があれば、

```ruby
ary.lazy.flatten.tally
```

とできて、良いのではないかと思いました。乱暴な書き方をすると、

```ruby

class Enumerator::Lazy
  def flatten
    flat_map(&:itself)
  end
end
```

的なものです。