From: Rudi Cilibrasi <cilibrar@...>
Date: 2008-07-03T12:31:51+09:00
Subject: thoughts on a more generic Array#partition function

An experiment in a more generic partition function.  The current
Array#partition function takes a code block and interprets the result
in a boolean way to create two lists.  What if the user wants to create
more than two lists?

A common idea is to define a sort of indicator function that maps each
element of the array to a value that indicates which list to assign the
element to.  Then, all elements that resulted in the same value would be
assigned the same partition list.  This is a good system, but has one
small problem: It cannot return the results in a definitely ordered
Array because there is no way to know what order the return values are unless
they are Sortable.  Since TrueClass and FalseClass are not sortable, it
means that it is hopeless to try to preserve compatibility with the old
partition function without extending the TrueClass and FalseClass to at
least allow <=> comparisons between true,true and true,false, etc.

Therefore, in this demonstration I want to show four points:

1) It is possible to write a generic partition function that can sort into
any number of lists and not just two.  This generic partition function,
called npartition, can use the boolean types true and false as
well as any integer, string, symbol, or other code block return types instead.
In the program below, I demonstrate using the boolean and integer modes to
partition a small array of integers.

2) A generic partition function  can be perfectly compatible with
the pre-existing two-way split partition function as long as users are
willing to apply a boolean cast in the cases where booleans are not
explicitly returned: return i must become return i ? true : false to be safe
in those cases that previously relied on a Boolean context cast.

3) It is impossible to have a non-array-data-dependent (canonical) ordering
for the returned partition lists unless we require the possible sorting
key (returned from code block) values to be Sortable.   If we do not require
this, then we would be forced to use the input key appearance sequence as
the output ordering and this would shift depending on which element is
listed first in the Array.  It is desirable to have a standard order that
occurs regardless of the order of appearance in the input array.  In fact,
the current partition function effectively imposes an ordering on the true
and false implicitly by its return ordering of true first then false.

4) It is convenient, therefore, to allow a (any) standard ordering to be
imposed on TrueClass and FalseClass.  By not imposing a standard ordering,
we make it difficult for others to do so in a safe way that won't conflict.
Yet, there are often cases where code could make great use of any particular
ordering for true,false as is implied by mathematical lattice theory.  It
would also be convenient to include nil in this ordering: true nil false
I cannot tell if this is possible in Ruby without breaking other things.
---------------------------------------------------------------------

class Array
  def npartition(&cb)
    labels = inject( { } ) { |n, a|
      k = cb.call(a)
      n[k] = [ ] unless n.has_key?(k)
      n[k] << a
      n
    }
    labels.keys.sort.map { |a| labels[a] }
  end
end

# returns a boolean sorting key given an integer
def bfunc(q)
  q % 2 == 0
end

# returns an integer sorting key given an integer
def ifunc(q)
  q % 2
end

# Reverse Alphabetical by class name for singleton classes only
def ofunc(sa, sb)
  sb.class.to_s <=> sa.class.to_s
end

def testpart(a)
  r1 = r2 = "failed"
  begin
    r1 = a.partition() { |i| yield i }
  rescue
    puts $!
  end
  puts "From partition: #{r1.inspect}"
  begin
    r2 = a.npartition() { |i| yield i }
  rescue
    puts $!
  end
  puts "From npartition: #{r2.inspect}"
end

  a = [ 1, 2, 3, 4, 7, 9, 11, 12, 13, 14 ]
puts "Without TrueClass FalseClass ordering extension:"
puts "Boolean case:"
testpart(a) { |i| bfunc(i) }
puts "Integer case:"
testpart(a) { |i| ifunc(i) }
class TrueClass
  def <=>(b) ofunc(self,b) end
end
class FalseClass
  def <=>(b) ofunc(self,b) end
end
puts "\nWith    TrueClass FalseClass ordering extension:"
puts "Boolean case:"
testpart(a) { |i| bfunc(i) }
puts "Integer case:"
testpart(a) { |i| ifunc(i) }

puts "\nSpecial (new extension) three-way list split"
testpart(a) { |i| i % 3 }
exit 0
------------------------------------------------------------------------------------
Git, Hg (Mercurial), and Subversion (svn) hosting over SSH
http://sshcontrol.com/