From: gotoken@... (GOTO Kentaro)
Date: 1998-07-07T12:30:45+09:00
Subject: [ruby-list:8640] Equivalence.rb

ごとけんです

同値類のとっても単純なモジュールを書きました。
需要があれば充実させて再度公開つもりですので、
御覧下さい。
# 早い段階で名前や実装への意見を頂こうと ^^;;

今のところ、引数かブロックで与えた同値関係の商を 
Family オブジェクトとして返す Equivalence#quotient 
しかありません。引数とブロックが省略されると
`===' を同値関係と仮定して、その商を返します。

Family#[] は代表元を与えるとその同値類を Array 
として返します。

Equivalence#quotient は each と、高速化のため
size と include? と delete を使います。
# 立石さん、石塚さんの意見はまだ活かされてません (__;

実例はこんな感じです(thanks `irb --prompt xmp'): 

  require "Equivalence"  # also let Array include Equivalence
      ==>true

  a = [1,2,3,4,5,6,7,8,9,10]  # simple Array
      ==>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

  q0 = a.quotient{|i,j| i%2 == j%2}
      ==>[[1, 3, 5, 7, 9], [2, 4, 6, 8, 10]]

  q0[1]  # equivalece class for the reprezentative 1
      ==>[1, 3, 5, 7, 9]

  q0[0]  # ditto for 0 (will be nil since !a.include? 0)
      ==>nil

-- gotoken

#
# Equivalence.rb
#

module Equivalence
  def quotient(rel = :===, &cmp)
    __res__ = []
    __dup__ = self.dup
    if iterator?
      each{|i|
	if (__dup__.include? i) && (__dup__.size > 0)
	  __res__ |= [foo = __dup__.find_all{|j| cmp.call(i,j)}]
	  foo.each{|i| __dup__.delete i}
	end
      }
    else
      each{|i|
	if (__dup__.include? i) && (__dup__.size > 0)
	  __res__ |= [foo = __dup__.find_all{|j| j.__send__(rel, i)}]
	  foo.each{|i| __dup__.delete i}
	end
      }
    end
    Family.new __res__
  end

  class Family
    def initialize(ary)
      @body = ary.sort
    end

    def inspect
      @body.inspect
    end

    def to_s
      @body.to_s
    end

    def [] x
      @body.find{|s| s.include? x}
    end

    def method_missing(id, *arg, &blk)
      @body.__send__(id, *arg, &blk)
    end
  end
end

class Array
  include Equivalence
end

# end of Equivalence.rb