[Haskell-cafe] Re: Announcing OneTuple-0.1.0

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