...

What is the basic philosophy for Bool being a member of Ord? you can do sth like

Data.Set.fromList [minBound .. maxBound] :: Data.Set.Set Bool Sorry, not quite sure what you mean.

...

What justifies False < True? in most interpretations this equals:

False == 0 True == 1 Indeed, it's the same in C but what justifies the decision in Haskell?

and == (*) or == max not == (1 -) a `xor` b == (a + b) `mod` 2

and not this:

False == 1 True == 0 and == max or == (*) not == (1 -) a `xor` b == (a + b) `mod` 2

Thanks, Paul

On Thu, May 31, 2007 at 10:03:05AM +0100, PR Stanley wrote:

...

...

What is the basic philosophy for Bool being a member of Ord?

I hear two questions, why is Bool a member of Ord at all, and why was it ordered with False before True. If I'm reading the reports correctly, the Ord instance was actually added in the Haskell 1.1 standard, by changing the definition of Bool from data Bool = True | False to data Bool = True | False deriving (Eq, Ord, Ix, Enum, Text, Binary) (Text was later broken into Read and Show) I imagine it was added because you generally can't derive an instance of a class for a new type unless all the types you mention in the definition already have instances. Also, there are Ord instances like (Ord a, Ord b) => Ord (a,b), and it's sometimes handy to be able to use types like (String, Bool) as keys in a Map, or keep them in a Set. Probably there are other useful things you can do.

...

...

What justifies False < True? in most interpretations this equals:

False == 0 True == 1

Indeed, it's the same in C but what justifies the decision in Haskell?

It seems like we actually get that order because deriving Ord makes constructors earlier in the definition compare greater than later constructors, and nobody was bothered by that ordering. I can't see how one of the orders could be more expressive or otherwise technically better than the other, so I suppose you might as well agree with other conventions. I think it's mathematical convention more than the C convention Haskell is agreeing with. But this is all just speculation - the members of the Haskell comittee could tell us why this all actually happened, and at least a few read this list. Brandon

...

I think it's mathematical convention more than the C convention Haskell is agreeing with.

I think so, too. In Boolean algebra (which predates computers, much less C), FALSE has traditionally been associated with 0, and TRUE with 1. And since 1 > 0, TRUE > FALSE. The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1? A Boolean value denotees veracity whereas an ordered value concerns magnitude (priority), indeed, order!! Thanks, Paul

On Thu, 31 May 2007, Paul Hudak wrote:

PR Stanley wrote:

...

...

I think so, too. In Boolean algebra (which predates computers, much less C), FALSE has traditionally been associated with 0, and TRUE with 1. And since 1 > 0, TRUE > FALSE. The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1?

Because if you take (&&) to be (*), and (||) to be (+), you get a homomorphism between the two resulting algebras (assuming 1+1 = 1).

It seems however, that if the number representations of False and True are flipped, then we only need to flip the interpretations of (&&) and (||). For me the choice fromEnum False == 0 && fromEnum True == 1 seems rather arbitrary. The conversion is certainly useful for writing Bool values to binary files. Maybe the Ord instance was introduced in order to be able to put Bools in Sets and Maps. However this confirms my doubts whether using Ord constraint for Sets and Maps was a good choice. http://www.haskell.org/pipermail/libraries/2007-April/007411.html

All these smart math guys hanging around and nobody's given a really decent answer to this? It's actually not arbitrary. There's a strong connection between predicates (functions that return boolean values) and sets. Any predicate uniquely determines a set - the set of values for which it returns true. Similarly, any set determines a predicate - one that returns true exactly when the argument is a member of the set. It's natural to define a partial order among sets from inclusion: A ≤ B iff A ⊆ B. Viewing the sets as predicates, the corresponding relationship between the predicates is implication. A ⊆ B iff (x ∊ A) ⇒ (x ∊ B) - so predicates are naturally ordered by implication. Viewed as sets, the predicate that always returns False is equivalent to ∅ - the empty set, while the predicate that always returns True is equivalent to U - the universal set that contains everything (in naive set theory, anyway - in axiomatic theories it gets a little more complicated). So, since "subset" gives a "natural" order to sets, "implication" gives a natural order to predicates, thus it's "natural" to say that the Haskell expressions (const False) and (const True), which are predicates, are ordered: (const False) < (const True). And therefore, it's natural to say that False < True. Anyway, that's my explanation for it. :) Derek Elkins wrote:

Henning Thielemann wrote:

...

On Thu, 31 May 2007, Paul Hudak wrote:

...

PR Stanley wrote:

...

...

I think so, too. In Boolean algebra (which predates computers, much less C), FALSE has traditionally been associated with 0, and TRUE with 1. And since 1 > 0, TRUE > FALSE.

The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1?

Because if you take (&&) to be (*), and (||) to be (+), you get a homomorphism between the two resulting algebras (assuming 1+1 = 1).

It seems however, that if the number representations of False and True are flipped, then we only need to flip the interpretations of (&&) and (||). For me the choice fromEnum False == 0 && fromEnum True == 1 seems rather arbitrary.

It -is- arbitrary, in boolean algebra as well. not is an automorphism between the two. However, we tend to think of 0 as associated with nothing/the empty set and that maps naturally to {x | False}. There are intuitive reasons why this choice was chosen, but no formal reasons. Obviously, there are pragmatic reasons to use this choice in programming languages, e.g. many languages use 0 to represent false and non-zero or 1 to represent true and this is consistent with that. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- ----- What part of "ph'nglui bglw'nafh Cthulhu R'lyeh wagn'nagl fhtagn" don't you understand?

On Tue, 2007-06-05 at 01:16 -0400, Albert Y. C. Lai wrote:

Scott Brickner wrote:

...

It's actually not arbitrary. [...] A ≤ B iff A ⊆ B A ⊆ B iff (x ∊ A) ⇒ (x ∊ B)

Alternatively and dually but equally naturally,

A ≥ B iff A ⊆ B iff (x ∊ A) ⇒ (x ∊ B)

and then we would have False > True.

Many of you are platonists rather than formalists; you have a strong conviction in your intuition, and you call your intuition natural. You think ∅≤U is more natural than ∅≥U because ∅ has fewer elements than U. (Why else would you consider it unnatural to associate ≥ with ⊆?) But that is only one of many natural intuitions.

There are two kinds of natural intuitions: disjunctive ones and conjunctive ones. The elementwise intuition above is a disjunctive one. It says, we should declare {0}≤{0,1} because {0} corresponds to the predicate (x=0), {0,1} corresponds to the predicate (x=0 or x=1), you see the latter has more disjuncts, so it should be a larger predicate.

However, {0} and {0,1} are toy, artificial sets, tractible to enumerate individuals. As designers of programs and systems, we deal with real, natural sets, intractible to enumerate individuals. For example, when you design a data type to be a Num instance, you write down two QuickCheck properties: x + y = y + x x * y = y * x And lo, you have specified a conjunction of two predicates! The more properties (conjuncts) you add, the closer you get to ∅ and further from U, when you look at the set of legal behaviours. Therefore a conjunctive intuition deduces ∅≥U to be more natural.

So as I said (not really directed at you Albert), there are intuitive reasons but no formal ones. And incidentally, implication was one of the first things mentioned in the thread.

On 05/06/07, PR Stanley wrote:

Hello What do the ≤ symbols represent?

'Less than or equal to'. To say that x ≤ y, if x and y are numbers, means that x is either less than y, or x and y are equal (so x cannot exceed y). However, in the spirit of mathematics, the symbol now actually means slightly more than just that. There's a general concept called a "partial order" which is quite important in all of mathematics, especially in computer science. Here ≤ still means 'less than or equal to', but that takes on a different meaning depending on which partial order you're talking about. For example, you can order sets by inclusion, so that {1, 2, 3} ≤ {1, 2, 3, 4, 5, 6} because {1, 2, 3} is a subset of {1, 2, 3, 4, 5, 6}. Or you could order the natural numbers by 'divisibility', i.e. you could say that x ≤ y if and only if x is a factor of y (so that 2 ≤ 4, and 3 ≤ 18). You could say that a function f ≤ another function, g, if and only if f(x) ≤ g(x) for every x. If you're familiar with denotational semantics, the partial order on expressions used there roughly corresponds to how many evaluation steps you've gone through, so that 1:2:<thunk> ≤ 1:2:3:4:<thunk>, and (<thunk>, <thunk>) ≤ ("hello", 4.3). The reason these are "partial" orders is because sometimes it makes no sense to say that x ≤ y, and it makes equally little sense to say that y ≤ x. For example, if you had the sets {1, 2} and {4, 5}, neither is a subset of the other, so {1, 2} ≤ {4, 5} is false, but {4, 5} ≤ {1, 2} is false, too. http://en.wikipedia.org/wiki/Partial_order contains a formal definition and a few more examples. -- -David House, dmhouse@gmail.com

Well, traditionally, a boolean algebra is a ring, which means it has two operations corresponding to plus and times, and a zero such that a plus zero is a, and a one such that a times one is a. Also by longstanding tradition, zero is less than one. Now, in most programming languages, a boolean type is an element of the two valued boolean algebra, but not all boolean algebras are two valued. Four valued boolean algebra, for example, introduces m and not m (which must be distinct). There the ordering is typically false, not m, m, true. Overall, you might as well ask why 'b' is greater than 'a'. Consistent and useful. On 6/5/07, Albert Y. C. Lai wrote:

PR Stanley wrote:

...

What do the ≤ symbols represent?

I see you are still stuck in ISO-8859-1 and deprived of international characters and symbols. (And this reply in ISO-8859-1 too accordingly; normally I use UTF-8.) Unicode and UTF-8 FTW! :)

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Wed, Jun 06, 2007 at 02:50:12AM +0100, PR Stanley wrote:

...

PR Stanley wrote:

...

What do the ??? symbols represent?

I see you are still stuck in ISO-8859-1 and deprived of international characters and symbols. (And this reply in ISO-8859-1 too accordingly; normally I use UTF-8.) Unicode and UTF-8 FTW! :)

oh very good, very good but forgive me, how is that supposed to answer my question? Paul

My mail reader also seems to lack proper unicode support. I could figure out what the symbols were (and verify the message arrived uncorrupted in UTF-8) by saving the message and using another program. Perhaps something similar would work for you. The unicode-bearing paragraph of Scott Bricker's message reads It's natural to define a partial order among sets from inclustion: A less-than or equal to B if and only if A subset of or equal to B. Viewing sets as predicates, the corresponding relationship between predicates is implication. A subset of or equal to B if and only if x element of A implies x element of B - so predicates are naturally ordered by implication. Viewed as sets, the predicate that always returns False is equivalent to empty set - the empty set, while the predicate that always returns True is equivalent to U - the universal set that contains everything (in naive set theory, anyway - in axiomatic theories it gets a little complicated). I replaced each unicode character with its name. I think the result reads pretty well. There ought to be programs for this, can anyone suggest Haskell libraries that would make one easy to write? Brandon

Another point worth noting is that the usual lambda calculus representations of false and zero are equivalent. (However true is not the same as one.) Tony. -- f.a.n.finch http://dotat.at/ MALIN: EAST OR SOUTHEAST 4 OR 5. MODERATE. FAIR. MODERATE OR GOOD.

On Fri, 01 Jun 2007 03:33:41 +0100, you wrote:

The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1?

There is a correspondence between a Boolean algebra and an algebraic ring. If we identify 0 with FALSE and 1 with TRUE, then that correspondence leads to a natural identification of addition with EXCLUSIVE OR, and multiplication with AND: 0 + 0 = 0 FALSE XOR FALSE = FALSE 0 + 1 = 1 FALSE XOR TRUE = TRUE 1 + 0 = 1 TRUE XOR FALSE = TRUE 1 + 1 = 0 TRUE XOR TRUE = FALSE (carry is ignored) 0 * 0 = 0 FALSE AND FALSE = FALSE 0 * 1 = 0 FALSE AND TRUE = FALSE 1 * 0 = 0 TRUE AND FALSE = FALSE 1 * 1 = 1 TRUE AND TRUE = TRUE

A Boolean value denotees veracity whereas an ordered value concerns magnitude (priority), indeed, order!!

It is frequently desirable to enumerate things, even when those things don't have a well-defined order. In such cases, we have to impose an order, perhaps arbitrarily. Within a given programming context, it doesn't matter what we choose for our enumeration order, but it's generally best to go along with whatever de facto standard there is, if for no other reason than to avoid going insane. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

PR Stanley wrote:

The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1? A Boolean value denotees veracity whereas an ordered value concerns magnitude (priority), indeed, order!!

Other members have mentioned how to do it either way. Certain people with strong convictions in philosophy, religion, or platonism are more happy to see "truth is greater than falsehood" than "falsehood is greater than truth". It would be nice if we could be user-friendly to them.

Brandon,

If I'm reading the reports correctly, the Ord instance was actually added in the Haskell 1.1 standard, by changing the definition of Bool from

data Bool = True | False

to

data Bool = True | False deriving (Eq, Ord, Ix, Enum, Text, Binary)

It's data Bool = False | True

It seems like we actually get that order because deriving Ord makes constructors earlier in the definition compare greater than later constructors, and nobody was bothered by that ordering.

It's the other way around: data T = Less | More deriving (Eq, Ord) gives you *Main> Less < More True Cheers, Stefan