Re: By The Dawn's Normal Light

From: Marshall Spight <mspight_at_dnai.com>
Date: Sun, 24 Oct 2004 15:23:33 GMT
Message-ID: <VNPed.240446$wV.26262_at_attbi_s54>


"Paul" <paul_at_test.com> wrote in message news:417ba93a$0$33600$ed2619ec_at_ptn-nntp-reader02.plus.net...
> Marshall Spight wrote:
> > It's funny: the RM has no facilities for handling lists; the Pick model
> > has no facilities for handling relations.
> >
> > Sometimes you have ordered data, and sometimes you have unordered
> > data. Which primitive operations you want depends on which one
> > you have. Each model handles one well and ignores the other.
> >
> > I propose that the ideal model would handle both, and have
> > relatively simple ways of transforming one into the other.
>
> I think the root of the problem is that lists require second-order
> logic. You could store a list in a relation with a predicate that says:
>
> Item X comes after Item Y.
>
> together with some constraints to say that only one item can come after
> any given item, no item can come after itself, there must be a start
> item, etc. plus a special value to indicate the start of the list.
>
> But then I think the constraint to stop loops (B follows A, C follows B,
> A follows C) would require second order logic. I might be wrong there
> though, maybe there's some clever way of doing it in first-order logic.

You've making it overly complicated. I find a simple reference to set theory and a good definition of list makes this a lot clearer.

List: "a mapping between the natural numbers and the elements of a set."

That's a weird definition if you're a programmer, but it makes sense after a while.

Note also that a finite list is a mapping from a contiguous subset of the natural numbers. Also note that the definition doesn't require that the mapping be one-to-one, so *you can't go the other way.* The reverse map is not a function; you can't indentify list elements without reference to their position.

A list is not the same thing as an ordered set. You're not just taking set members and putting them in an order; you're mapping from the nats to the set.

Consider this list of characters: "john obeys army"

Does the character 'o' follow the character 'n'? The question is meaningless, because I haven't said which 'o'. If we treat the above as a set, the *index* is the key, not the characters.

If this were an ordered set, we would have a boolean function (alternatively, a relation) 'less than' (or, in the case of a partially ordered set, 'less than or incomparable') that would tell us whether element A preceeds element B. The no-loops property would follow from the definition of the function, which would have to be transitive.

I haven't covered all the ground yet but I'm starting to bore myself.

Marshall Received on Sun Oct 24 2004 - 17:23:33 CEST

Original text of this message