[Haskell-cafe] Re: Announcing OneTuple-0.1.0

Actually, on second thought, there might be one problem with using nested tuples in cpos in Haskell: Each tuple would have a different type. I.e., if we let X /= (X) /= ... /= (..(^nX)..)^n then :type X would yield a different result from :type (X) which would yield a different result from :type ((X)) which would yield a different result from ... which would yield a different result from :type (..(^nX)..) (using my notation here). It might then be difficult to order the tuples of different nesting.... I may need to think of a way around this issue.... -- Benjamin L. Russell --- On Fri, 10/3/08, Benjamin L. Russell wrote:

From: Benjamin L. Russell Subject: Re: Announcing OneTuple-0.1.0 To: Date: Friday, October 3, 2008, 3:10 PM On Thu, 2 Oct 2008 14:46:32 -0700, "Jason Dusek" wrote:

...

John Dorsey wrote:

...

Now you can: * Solve any of the software problems that cannot be solved without the singleton tuple !

What would those be? I'm still trying to figure out how a singelton tuple is really distinct from a plain value.

Actually, part of my original motivation for suggesting a singleton tuple had to do with in using it as a tool for modeling complete partial orders (a.k.a. "cpos") (see http://en.wikipedia.org/wiki/Complete_partial_order), such as those that appear in a lattice (see http://en.wikipedia.org/wiki/Lattice_(order)). A lattice is a partially ordered set in which every pair of elements has a unique supremum (see http://en.wikipedia.org/wiki/Supremum) and infimum (see http://en.wikipedia.org/wiki/Infimum).

When I was in college, one of the courses that I took was on domain theory (see http://en.wikipedia.org/wiki/Domain_theory), where we used complete partial orders to model (partial) results of a computation, where elements higher in the order extended the information of the elements below them in a consistent way. _|_ (bottom) represented an undefined result, and, if present in a cpo, was a least element for that cpo.

In a lattice, unlike in a list, since every pair of elements has a unique supremum and infimum, it is possible to have an ordering where a pair of elements X1, Y1 < Z1 for some element Z1, and X1, Y2 < Z2 for some other elements Y2, Z2, but neither Z1 < Z2 nor Z2 < Z1. This kind of ordering cannot be represented in a list in which every element is a number.

My idea was that it may be possible to use nesting of tuples to represent this kind of ordering if we, say, allow nesting an element in a tuple to distinguish that element from the same element not nested in a tuple, and to define elements or tuples X to have a lower ordering than either the same elements or tuples X with more nesting (e.g., X < (X)), or less than elements containing either those elements or containing tuples containing those elements (e.g., X < (X) and X < ((X), (Y)) (in the above-mentioned example) (() as _|_ being a unique least element).

E.g. (in the above-mentioned example), let:

X1 = (X) Y1 = (Y) Y2 = ((Y))

Then, in order to define Z1 and Z2, since

X1 < Z1, Y1 < Z1 i.e., (X) < Z1, (Y) < Z1

and

X1 < Z1, Y2 < Z2 i.e., (X) < Z1, ((Y)) < Z2

just define:

Z1 = ((X), (Y)) Z2 = ((X), ((Y)))

Then:

X1 < Z1 i.e., (X) < ((X), (Y))

and

Y1 < Z1 i.e., (Y) < ((X), (Y))

and

X1 < Z2 i.e., (X) < ((X), ((Y)))

Y2 < Z2 i.e., ((Y)) < ((X), ((Y)))

but not: Z1 < Z2 i.e., not: ((X), (Y)) < ((X), ((Y))) (since they cannot be compared)

and not: Z2 < Z1 i.e., not: ((X), ((Y))) < ((X), (Y)) (again, since they cannot be compared)

Forgive me if this makes little sense, but I just thought that being able to define, say, (X) = X1 < ((X)) = X2 < (((X))) = X3 < .. < (..(^nX)..)^n = Xn

would be useful in this kind of ordering.

Then, X is not the same as (X), because X = X0, (X) = X1, ..., (..(^nX)..)^n = Xn, and in the context of this example, X < (X) < ... < (..(^nX)..)^n.

Having a singleton tuple might then allow the representation of lattices using tuples, in which _|_ (bottom) = () is a unique least element, and for each element X in the lattice, X < (X) and X < each tuple containing X.

Without a singleton tuple, we cannot define X < (X), because then X = (X).

Does this sound plausible?

-- Benjamin L. Russell