[Haskell-cafe] Re: Announcing OneTuple-0.1.0

[Benjamin L.Russell]

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 <DekuDekuplex at Yahoo.com>
wrote:

> From: Benjamin L. Russell <DekuDekuplex at Yahoo.com>
> 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"
> <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