[Haskell-cafe] Re: Announcing OneTuple-0.1.0
Benjamin L.Russell
DekuDekuplex at Yahoo.com
Fri Oct 3 02:10:43 EDT 2008
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
More information about the Haskell-Cafe
mailing list