[Haskell-cafe] Re: Announcing OneTuple-0.1.0

[Benjamin L.Russell]

On Thu, 2 Oct 2008 14:46:32 -0700, "Jason Dusek"
<jason.dusek at gmail.com> wrote:

>John Dorsey <haskell at colquitt.org> 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