From: cilibrar@... (Rudi Cilibrasi)
Date: 2002-10-28T19:49:20+09:00
Subject: Re: How come true, false don't support <=> (comparison) operator?

You're right; I've made a simple example that seems to have distracted
you from my point.  It is not so obvious why I would want to sort an
array of boolean values, as I could just count.  The actual need I
came across in my programming was, rather, having to sort an Array
of Arrays of booleans.  In this case, I have entries of the form

true
false false
true false true
false
and so on.

This is different from what I could do easily with integers, in that
any
number of falses all in a row is still equal to the integer value 0.
Arrays carry an explicit length indicator, integers do not.
I want different numbers of falses in succession to be considered
different bit strings, as is the case in formal mathematics.  I don't
agree with the "cultural relativist" idea that since we can't say
which should be first, true or false, we shouldn't order them.  By
default, when you compare a String, you get forward alphabetical
order, not backward, because that is what more people expect, not
because
there is some deeper structure in Ruby that says alphabetical order is
right.  Any default order is better than none for finite sets; those
that don't like it don't need to compare booleans for ordering, or
can override the default ordering with their own; To me, the important
question is if this enhancement is likely to surprise people with
unexpected behaviour; I am interested to hear any such hypotheticals.

The very fact that ruby has words for 'and' and 'or', symbols for &,
&&, |,
and ||, true, and false, implies that it seeks to be compatible with
Boolean algebra.  In math, oftentimes the "or" operation is
represented with +, and the "and" operation with *.  The reason this
is done is because then certain laws work for Boolean algebra.  To be
exact,
If you say:
* is and
+ is or
0 is false
1 is true
Then you can say
a*1 = 1*a = a (conveniently the same as general algebra)
a+0 = 0+a = a (again mnemonically convenient)
a*0 = 0       (just like regular times)
a+1 = 1       (this is unique to Boolean algebra)
a*(b+c) = a*b + a*c
a+(b*c) = (a+b) * (a+c)

Notice that you need to decide the difference between "true" and 
"false" in order to distinguish between "and" and "or"; both binary
operations are a type of "meet operator" heading toward one end or the
other of a boolean lattice, and they are structurally equivalent,
e.g.,
!((!a)*(!b)) = a+b. And given that we do, in fact, have to break
the symmetry, I don't see any reason not to do so in the most accepted
fashion based on literature in logic and lattice theory.  The to_i
functions I wrote are not, themselves, important; they were just the
easiest way for me to express the <=> relationship clearly.  For those
that are interested in the exact definition of a boolean algebra,
you can find a good one at
http://plato.stanford.edu/entries/boolalg-math/
where you can see that they do use 0 and 1 to represent false and true
in the above identities.  This page also mentions the natural ordering
that all Boolean algebras have:

Any BA has a natural partial order defined upon it by saying 
that x <= y if and only if x + y = y.

This is another way of saying false is less than true.
I think it is an error of omission to not include this natural
ordering
in Ruby.

Rudi

Greg McIntyre <greg@puyo.cjb.net> wrote in message news:<20021026012257.4aa18f21.greg@puyo.cjb.net>...
> > true <=> false  (should be +1 or -1)
> > false <=> false (should be 0)
> 
> I agree with David. They don't make sense in general (except maybe the
> latter one), as booleans have no ordinality.
> 
> 
> > Another common thing I find myself needing is to sort these, like:
> > a.sort!
> 
> I don't usually belabour efficiency, but isn't this horrendously
> inefficient? Correct me if I'm wrong, but assuming #sort is a quicksort,
> this is O(nlogn) whereas you could simply iterate through the bits and
> collect two groups, one of 'trues' and one of 'falses' and then
> concatenate them, which would be O(n).
> 
> Maybe that's just me.
> 
> 
> > I have used the following code to make these operations work:
> > class TrueClass
> >   def to_i() 1 end
> >   def <=>(b)
> >     to_i <=> b.to_i
> >   end
> > end
> > class FalseClass
> >   def to_i() 0 end
> >   def <=>(b)
> >     to_i <=> b.to_i
> >   end
> > end
> 
> Personally I don't like these as we have true and false classes for a
> reason. I mean... if you want to use integers, use integers. If you want
> a convenient but inefficient representation for a bitstring you can
> sort, use arrays of integers. The only reason you'd want to use true and
> false is that they better reflect what you're doing... but not if you
> defeat that purpose by converting back to integers for every operation.
> 
> That's my 2c, anyway.