Re: Range types

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wed, Dec 16, 2009 at 04:45:54PM -0300, Alvaro Herrera wrote:
> tomas(at)tuxteam(dot)de wrote:
>
> > (and as Andrew Dunstan pointed out off-list: I was wrong with my bold
> > assertion that one can squeeze infinitely many (arbitrary length)
> > strings between two given. This is not always the case).
>
> Of course you can do that if you assume lexicographical order, or any
> other arbitrary order.

Hm. On strings (lexicographical order) there's always a "next" (using
the convention 'a' is the first symbol, 'z' the last and . the append
operator):

next(X) == X . 'a'

(there is no string between X and X . 'a', and X < X . 'a')

But there generally no prev! (unless the last "character" of a string is
precisely 'a')

prev("bob") == "bazzzzz......"

...and we just left the realm of finte-length strings. Strange structure
this space, has.

> some ordering on which this does not happen. And in fact there is:
> order strings by length first, and then lexicographically. If you do
> this then you have next() and prev() for any given string. If you use
> ASCII only, you have a.next = b, and so on.

Yes, this is similar to the trick of ordering the rationals in a "snake
diagonal" like in [1], to prove their countability. But this sorting
isn't very useful (except in this clever proof).

> There is the argument that some languages do not sort lexicographically
> but this is also besides the point [...]

Totally agree.

> Defining strings with this ordering means you can have some useful
> ranges like [a-z], but then you cannot meaningfully use ranges for
> things like [aardvark - zulu] --- note that in this particular example,
> the order is reversed, because zulu comes before aardvark which is
> probably not what you want. zzz.next = aaaa

Yep. Its just useful to prove that the set of strings is countable (I
wonder whether our world would be different if we had chosen the
convention of looking up words in this "length+lexicographical" order in
the first place -- it reminds me of how Chinese-speaking people look up
symbols in a dictionary: number of strokes first).

> In short, I think that while it is possible to define ranges of strings,
> it is not as useful as one would like.

Unless you are willing to treat strings as non-discrete, somehow.

Regards
- ----------------
[1] <http://en.wikipedia.org/wiki/Rational_numbers#Properties>

- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFLKbiFBcgs9XrR2kYRAnUYAJ0QBbWzNITA1KARLKdPTshFBSp/ZwCeIbin
Lwc/pRBYgKoaccGpn0beyu4=
=nViD
-----END PGP SIGNATURE-----