[ruby-dev:42638] Enumerable#categorize

enumerable から hash を生成するメソッドとして
Enumerable#categorize を追加するのはどうでしょうか。

まだ Ruby で試しに実装した段階で、C では実装していないので、すぐにという話ではありませんが。

categorize メソッドは enumerable の要素をカテゴリ分割して
hash を生成するメソッドです。

たとえば、以下のような配列があったとしましょう。
(より現実的な状況を想定するなら、CSV ファイルを CSV.read
で読み込んだ結果こういう配列が得られたと考えてください)

  ary = [
    ["matz", "Yukihiro Matsumoto"],
    ["nobu", "Nobuyoshi Nakada"],
    ["akr", "Tanaka Akira"],
    ["usa", "Usaku NAKAMURA"],
    ["naruse", "NARUSE, Yui"],
    ["ko1", "SASADA Koichi"]
  ]

こういうデータから、各要素の第一要素から第二要素、
あるいは第二要素から第一要素へのハッシュを作るというのはありがちな話です。

幸いにして第一要素から第二要素へのハッシュは Hash[ary] で作れるようになったので、
逆の第二要素から第一要素へのハッシュについて考えましょう。
(同姓同名を考慮して、ハッシュの値は第一要素の配列としましょう)

これを得るには現在、残念な事に、自分でループを書く必要があります。

  h = {}
  ary.each {|a, b|
    (h[b] ||= []) << a
  }
  pp h
  #=> {"Yukihiro Matsumoto"=>["matz"],
       "Nobuyoshi Nakada"=>["nobu"],
       "Tanaka Akira"=>["akr"],
       "Usaku NAKAMURA"=>["usa"],
       "NARUSE, Yui"=>["naruse"],
       "SASADA Koichi"=>["ko1"]}

Enumerable#categorize はこれをひとつのメソッド呼び出しで実現します。

  h = ary.categorize(1, 0)
  pp h
  #=> {"Yukihiro Matsumoto"=>["matz"],
       "Nobuyoshi Nakada"=>["nobu"],
       "Tanaka Akira"=>["akr"],
       "Usaku NAKAMURA"=>["usa"],
       "NARUSE, Yui"=>["naruse"],
       "SASADA Koichi"=>["ko1"]}

引数の 1, 0 が何を意味するかというと、enumerable の要素から
ハッシュのキー及び値を取り出す指定です。
具体的には ary の各要素に対し、[] メソッドを呼び出し、
その引数に引き渡してキー/値を得ます。
つまり、["matz", "Yukihiro Matsumoto"][1] として "Yukihiro Matsumoto" というキーを得て、
["matz", "Yukihiro Matsumoto"][0] として "matz" という値を得るわけです。

Enumerable#categorize の基本的な使い方はここまでなのですが、いくつか追加機能があります。

* 引数に Proc オブジェクト (正確には call メソッドを持ったオブジェクト) を指定すると、
  [] メソッドでなく、その Proc オブジェクトでキー/値を取り出す

  つまり、ary.categorize(1, 0) は
  ary.categorize(lambda {|elt| elt[1] }, lambda {|elt| elt[0] }) と同じです。

  Hash[ary] のような機能が何回もリクエストされながら長年実現されなかった理由は、
  要素が長さ2の配列であるという仮定を置いたメソッドに対する躊躇があったように思えるのですが、
  この Proc オブジェクトによる指定を可能にすることにより、
  Enumerable#categorize は要素に対する仮定を必須ではなくしています。

* ネストしたハッシュの生成

  [ruby-talk:372481] や [ruby-talk:288931] など、たまにあるのですが、
  ネストしたハッシュが必要な事があります。
  Enumerable#categorize のキーを指定する引数は、実はふたつ以上指定できて、
  そうするとネストしたハッシュを生成します。

  h = ary.categorize(lambda {|e| e[0][0] }, lambda {|e| e[0][1]}, 0)
  pp h
  #=> {"m"=>{"a"=>["matz"]},
       "n"=>{"o"=>["nobu"], "a"=>["naruse"]},
       "a"=>{"k"=>["akr"]},
       "u"=>{"s"=>["usa"]},
       "k"=>{"o"=>["ko1"]}}

* ハッシュの値の後処理

  ハッシュの値は配列ですが、その配列をソートしたいなどの後処理がしたいことがあります。
  そこで、Enumerable#categorize にブロックをつけると、
  生成した配列から他の値に変換することができます。

  h = ary.categorize(lambda {|e| e[0][0] }, 1) {|ks, vs| vs.sort }
  pp h'
  {"m"=>["Yukihiro Matsumoto"],
   "n"=>["NARUSE, Yui", "Nobuyoshi Nakada"],
   "a"=>["Tanaka Akira"],
   "u"=>["Usaku NAKAMURA"],
   "k"=>["SASADA Koichi"]}

  また、使う側としては同じキーに対してはひとつの値しかない事を知っていて
  配列にしたくないとか、
  あるいは合計・最小値・最大値・平均値が欲しいとか、また単に要素数だけ欲しいとか、
  そういう用途にも使えます。
  (これらについてはメモリ効率の点から次に述べる :seed, :op, :update を使う方が適切ですが)

  h = ary.categorize(1, 0) {|ks, vs|
    raise "duplicate keys: #{ks.inspcet}" if vs.length != 1
    vs[0]
  }
  pp h
  #=> {"Yukihiro Matsumoto"=>"matz",
       "Nobuyoshi Nakada"=>"nobu",
       "Tanaka Akira"=>"akr",
       "Usaku NAKAMURA"=>"usa",
       "NARUSE, Yui"=>"naruse",
       "SASADA Koichi"=>"ko1"}

  なお、ブロック引数の ks は生成された値に対応するキーの配列で、
  上記の例では、ひとつの値しかないはずなのにそうでなかったときの
  例外メッセージに使っています。

* :seed, :op, :update オプション

  メモリ消費の都合上、配列を生成したくない、という状況もあります。
  例えば、いくつあるのか数えたいというだけなら、
  配列を生成してから length を呼び出すのはかなり無駄です。
  そのような状況に対応するため、配列を生成するかわりの操作を指定することができます。

  h = ary.categorize(lambda {|e| e[0][0] }, lambda {|e| 1 }, :op=>:+)
  pp h
  #=> {"m"=>1, "n"=>2, "a"=>1, "u"=>1, "k"=>1}

  :seed と :op はだいたい inject のような動作になります。
  :update は :op とほぼ同じですが、引数がひとつ多くて、値に対応するキーが与えられます。
  (:seed が与えられない時には、各カテゴリの最初の値が seed 扱いになります)

  :op, :update に指定したものは to_proc で変換されるので、
  :op => :+ というのは、lambda {|x,y| x + y } の意味です。

* 複数の値を取り出す

  enum の要素が配列やハッシュで多くの要素をもつ場合、
  ひとつでなく、いくつかの要素を取り出すことがあります。
  そのために、配列を指定した場合には再帰的に要素の取り出しを行って、
  取り出した値を配列にまとめます。

  前述の ary は 2要素しかなく、あまりこれを適用する意味がないので、
  http://coderepos.org/share/export/38695/lang/ruby/ruby-committers/ruby-committers.yml
  を使うと、これはハッシュを要素とするの配列なので、

  committers = open("ruby-committers.yml") {|f| YAML.load(f) }
  pp committers.categorize("account", ["name", "nick"]) {|ks, vs| vs[0] }
  #=> {"matz"=>[["松本行弘", "まつもとゆきひろ", "Yukihiro Matsumoto"], ["Matz"]],
       "H_Konishi"=>[["小西弘将", "KONISHI Hiromasa"], nil],
       "aamine"=>[["青木峰郎", "Minero Aoki"], ["青木さん"]],
       ...

  などとでき、name と nick を両方取り出すことができます。
  (categorize の引数が整数じゃなくて文字列になっているのは ary の要素が文字列をキーとするハッシュだからです)

どうでしょうか。

配列から hash を生成するメソッドは現状 enum.group_by や Hash[assoc] がありますが、
categorize の狙い所としては、それらよりも低レベルで広い応用を持つが、いくらか記述が長く、
でもループで記述するよりは高レベルでかなり短い、というあたりです。

たとえば、 (1..6).group_by {|i| i % 3 } は
(1..6).categorize(lambda {|e| e % 3}, lambda {|e| e}) と実現でき、
Hash[ [ ["a", 100], ["b", 200] ] ] は
[ ["a", 100], ["b", 200] ].categorize(0, 1, :op=>lambda {|x,y| y }) と実現できます。
(あるいは配列ができちゃうけど [ ["a", 100], ["b", 200] ].categorize(0, 1) {|ks, vs|
vs.last } とか)

参考:
* RDB の hash-join アルゴリズム
* SQL の集約関数
* MapReduce

Ruby による試験的な実装:

module Enumerable
  # :call-seq:
  #   enum.categorize(ksel1, ksel2, ..., vsel, [opts])
  #   enum.categorize(ksel1, ksel2, ..., vsel, [opts]) {|ks, vs| ... }
  #
  # categorizes the elements in _enum_ and returns a hash.
  # This method assumes multiple elements for a category.
  #
  # +categorize+ takes one or more key selectors,
  # one value selector and
  # an optional option hash.
  # It also takes an optional block.
  #
  # The selectors specify how to extract a value from an element in _enum_.
  #
  # The key selectors, _kselN_, are used to extract hash keys from an element.
  # If two or more key selectors are specified, the result hash will be nested.
  #
  # The value selector, _vsel_, is used for the values of innermost hashes.
  # By default, all values extracted by _vsel_ from the elements which
  # key selectors extracts same value are composed as an array.
  # The array is set to the values of the innermost hashes.
  # This behavior can be customized by the options: :seed, :op and :update.
  #
  #   a = [{:fruit => "banana", :color => "yellow", :taste => "sweet",
:price => 100},
  #        {:fruit => "melon", :color => "green", :taste => "sweet",
:price => 300},
  #        {:fruit => "grapefruit", :color => "yellow", :taste =>
"tart", :price => 200}]
  #   p a.categorize(:color, :fruit)
  #   #=> {"yellow"=>["banana", "grapefruit"], "green"=>["melon"]}
  #   p a.categorize(:taste, :fruit)
  #   #=> {"sweet"=>["banana", "melon"], "tart"=>["grapefruit"]}
  #   p a.categorize(:taste, :color, :fruit)
  #   #=> {"sweet"=>{"yellow"=>["banana"], "green"=>["melon"]},
"tart"=>{"yellow"=>["grapefruit"]}}
  #   p a.categorize(:taste, :color)
  #   #=> {"sweet"=>["yellow", "green"], "tart"=>["yellow"]}
  #
  # In the above example, :fruit, :color and :taste is specified as selectors.
  # There are several types of selectors as follows:
  #
  # - object with +call+ method (procedure, etc.): extracts a value
from the element by calling the procedure with the element as an
argument.
  # - array of selectors: make an array which contains the values
extracted by the selectors.
  # - other object: extracts a value from the element using +[]+
method as +element[selector]+.
  #
  # So the selector :fruit extracts the value from the element
  # {:fruit => "banana", :color => "yellow", :taste => "sweet", :price => 100}
  # as {...}[:fruit].
  #
  #   p a.categorize(lambda {|elt| elt[:fruit][4] }, :fruit)
  #   #=> {"n"=>["banana", "melon"], "e"=>["grapefruit"]}
  #
  # When the key selectors returns same key for two or or more elements,
  # corresponding values extracted by the value selector are combined.
  # By default, all values are collected as an array.
  # :seed, :op and :update option in the option hash customizes this behavior.
  # :seed option and :op option is similar to Enumerable#inject.
  # :seed option specifies an initial value.
  # (If :seed option is not given, the first value for each category
is treated as an initial value.)
  # :op option specifies a procedure to combine a seed and an element
into a next seed.
  # :update option is same as :op option except it takes three
arguments instead of two:
  # keys, seed and element.
  # +to_proc+ method is used to convert :op and :update option to a procedure.
  # So a symbol can be used for them.
  #
  #   # count categorized elements.
  #   p a.categorize(:color, lambda {|e| 1 }, :op=>:+)
  #   #=> {"yellow"=>2, "green"=>1}
  #
  #   p a.categorize(:color, :fruit, :seed=>"", :op=>:+)
  #   #=> {"yellow"=>"bananagrapefruit", "green"=>"melon"}
  #
  # The default behavior, collecting all values as an array, is
implemented as follows.
  #   :seed => nil
  #   :update => {|ks, s, v| !s ? [v] : (s << v) }
  #
  # :op and :update option are disjoint.
  # ArgumentError is raised if both are specified.
  #
  # The block for +categorize+ method converts combined values to
final innermost hash values.
  #
  #   p a.categorize(:color, :fruit) {|ks, vs| vs.join(",") }
  #   #=> {"yellow"=>"banana,grapefruit", "green"=>"melon"}
  #
  #   # calculates the average price for fruits of each color.
  #   p a.categorize(:color, :price) {|ks, vs| vs.inject(0.0, &:+) / vs.length }
  #   #=> {"yellow"=>150.0, "green"=>300.0}
  #
  def categorize(*args, &reduce_proc)
    opts = args.last.kind_of?(Hash) ? args.pop : {}
    if args.length < 2
      raise ArgumentError, "needs 2 or more arguments without option
hash (but #{args.length})"
    end
    value_selector = cat_selector_proc(args.pop)
    key_selectors = args.map {|a| cat_selector_proc(a) }
    has_seed = opts.include? :seed
    seed_value = opts[:seed]
    if opts.include?(:update) && opts.include?(:op)
      raise ArgumentError, "both :op and :update option specified"
    elsif opts.include? :update
      update_proc = opts[:update].to_proc
    elsif opts.include? :op
      op_proc = opts[:op].to_proc
      update_proc = lambda {|ks, s, v| op_proc.call(s, v) }
    else
      has_seed = true
      seed_value = nil
      update_proc = lambda {|ks, s, v| !s ? [v] : (s << v) }
    end
    result = {}
    each {|*elts|
      elt = elts.length <= 1 ? elts[0] : elts
      ks = key_selectors.map {|ksel| ksel.call(elt) }
      v = value_selector.call(elt)
      h = result
      0.upto(ks.length-2) {|i|
        k = ks[i]
        h[k] = {} if !h.include?(k)
        h = h[k]
      }
      lastk = ks.last
      if !h.include?(lastk)
        if has_seed
          h[lastk] = update_proc.call(ks, seed_value, v)
        else
          h[lastk] = v
        end
      else
        h[lastk] = update_proc.call(ks, h[lastk], v)
      end
    }
    if reduce_proc
      cat_reduce(result, [], key_selectors.length-1, reduce_proc)
    end
    result
  end

  def cat_selector_proc(selector)
    if selector.respond_to?(:call)
      selector
    elsif selector.respond_to? :to_ary
      selector_procs = selector.to_ary.map {|sel| cat_selector_proc(sel) }
      lambda {|elt| selector_procs.map {|selproc| selproc.call(elt) } }
    else
      lambda {|elt| elt[selector] }
    end
  end
  private :cat_selector_proc

  def cat_reduce(hash, ks, nestlevel, reduce_proc)
    if nestlevel.zero?
      hash.each {|k, v|
        ks << k
        begin
          hash[k] = reduce_proc.call(ks.dup, v)
        ensure
          ks.pop
        end
      }
    else
      hash.each {|k, h|
        ks << k
        begin
          cat_reduce(h, ks, nestlevel-1, reduce_proc)
        ensure
          ks.pop
        end
      }
    end
  end
  private :cat_reduce
end

-- 
[田中 哲][たなか あきら][Tanaka Akira]