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