From: Christoph Rippel <chr@...>
Date: 2000-12-04T07:22:16+09:00
Subject: [ruby-talk:6786] Re: Array Intersect (&) question

Hi,

some of the examples in this thread are misleading since the elements of the
are always comparable.  What should be a natural order of  [Array,"a",13] &
["a",13,Array] ->  ?.

Here is a naive (but semantically correct) implementation  of  ``Set''
together with a conversion method

class Hash # as Set
def &(other)
    set={}
     each_key do |i|
        set[i]= 1 if other.member?(i)
     end
     set
end
# implement other set operations
end

class Array
def to_set
     set = {}
     each do |i|
     	set[i]  = 1
     end
     set
end
end


To say that the Array intersection is compatible with a mathematical set
theoretic intersection boils down to an equality of

 (a & b).to_set == a.to_set & b.to_set

for all Array objects a,b. The order and multiplicity of a & b is of no
relevance at all. If one  wants to achieve compatibility with the
mathematical multi set interpretation (essentially Hashes with values  in
[1,2,3 .. ] ) the same equations must hold with to_set replaced by to_mset.
Note this time multiplicity matters but the order is still irrelevant.

class Hash # as Multiset
def &(other)
    		set={}
    		each_key do |i|
        			set[i]= min(self[i],other[i]) if other[i]
      		end
    		set
	end
# implement other multi set methods
private
def min(n,m)
        		(n<m ) ? n : m
	end
end

class Array
	def to_mset
    	mset = {}
     		each do |i|
     			mset[i]= mset[i].succ
     		end
     	return mset
	end
private
	def nil.succ
    	1
	end
end

My point is that to expect a particular behavior of a & b is essentially a
matter of taste. The  default method probably should simply be efficient. To
make everybody happy one could also introduce flags along the lines of
class Array
def &(other, ordered=false, multi=false)
..
end
end
To get the no default behavior one would be forced into writing
a.&(b,true) - I guess also a matter of taste.

It is a quite different matter to expect that the intersection of (weakly)
ordered lists with comparable elements are also a (weakly) ordered list but
ruby does not really have this data structure in it core languages. (I guess
Ranges qualify as ordered lists).

Christoph