Missing `Ord Bool` instance

[RyanGlScott]

I was surprised to discover that Bool has an Eq instance, but not an Ord instance:

https://github.com/B-Lang-org/bsc/blob/3683cf35d3f6f05528f87db5085ba985b7c6f7d0/src/Libraries/Base1/Prelude.bs#L1259-L1260

Any reason not to include an Ord instance like the one for Haskell's Bool?

[quark17]

Ord isn't included in the deriving clause because BSC doesn't support deriving Ord. However, I also don't see a manually written instance. I can't think of a reason why we couldn't include such an instance.

Note that there are many other data types in Prelude that also don't have Ord instances, so I assume you'd want to define an instance for those too: Maybe, Either, List, File, Ordering, and more. Not to mention data types in other libraries, like Vector.

I think it's common to take some data and check it against some other value, and if that's a struct with a Bool/Maybe/Either field, then Bool/Maybe/Either needs Eq. But there's far less need for Ord (and its definition would be somewhat arbitrary) -- in Haskell, I assume it gets used for things like tree-like data structures, where you want to sort data into the leaves of the tree and it doesn't matter the order as long as there's a consistent one; or other places where you want to have a canonical ordering. If that's happeneing in hardware, you can always pack the data to bits, which has an Ord instance. It's less likely that people are writing non-hardware elaboration-time data structures, which may be why it hasn't been needed yet -- or maybe people defined their own instance as a workaround and didn't report it.

[rsnikhil]

What would be a good use case for Bool being in Ord? I don't think of the values True and False being ordered in either direction. Or, to put it another way, why is Bool in Ord in Haskell?

[quark17]

What would be a good use case for Bool being in Ord? I don't think of the values True and False being ordered in either direction. Or, to put it another way, why is Bool in Ord in Haskell?

I agree that Bool does not have a natural ordering, and thus any instance of Ord for it would be arbitrary. (And I would be equally OK with rejecting the addition of an Ord instance on that grounds, as I would be with accepting the addition of an instance.)

In Haskell, there have been some cases where an Ord instance is used not because the ordering has meaning, but just because some ordering (any ordering) is needed. The example that comes to mind is OrdMap. This implemented a mapping from keys of type k to values of type a. It was made obsolete by better Map libraires. But the idea was that a naive Map can be implemented with List (k,a) assuming Eq k, but this requires walking over the whole list to do a lookup; to speedup lookup, we could store the pairs in a binary tree, and we go left or right depending on whether the key being looked up is greater than or less than the node we're at. This OrdMap k a required Ord k -- it doesn't matter what the ordering is, just that it has some order. If I wanted the keys to be Either Integer Real, then Either would need an instance of Ord, which would be an arbitrary ordering (as, like Bool, there is no natural ordering). To motivate why Bool needs Ord, you could imagine that the keys are some struct, with Bool fields, say?

Another possibility is that you can remove duplicates from a list quicker by sorting it first. For this purpose, it doesn't matter what the order is, as long as there's some canonical ordering.

[RyanGlScott]

My use case for an Ord Bool instance is rather simple: I am randomly generating test cases of the form p1 >= p2, p1 > p2, etc., where p1 and p2 are random Bool-values expressions. This works well enough when generating C code, where booleans are just integers in disguise. Doing something similar when generating Bluespec code doesn't work out of the box, however, since you can't do this unless Bool has an Ord instance.

Admittedly, this is a somewhat unusual use case, and I can work around the limitation by simply restricting what kinds of test cases I generate for Bluespec to avoid generating things like p1 >= p2. Still, it would be nice not to have to have special-casing just for Bluespec code, and all it would take is adding an Ord Bool instance. (Adding other Ord instances would be nice for the reasons described in https://github.com/B-Lang-org/bsc/issues/665#issuecomment-1897550215, but I don't have a pressing need for them right now.)

[quark17]

If p1 and p2 are Bool, can you workaround it by doing pack(p1) >= pack(p2)?

[quark17]

Or just add an Ord#(Bool) instance in your own code?

[RyanGlScott]

Certainly, I can work around the lack of an Ord Bool instance on my end. It would be nice to have one so as not to add special casing on my end, but I won't lose much sleep if I have to do so.