Re: More on lists and sets

Jan Hidders wrote:
> Marshall Spight wrote:
> >
> > So I would propose that we need to consider sorting with partial
> > orders and sorting with totals orders separately. In the total order
> > case, we end up with a list whose element type is the same as
> > the element type of the set. In the partial order case, we end up
> > with a list-of-sets, where the set has cardinality-1 in the no-ties
> > case and cardinality > 1 in the case of ties.
>
> Such a grouping seems more logical to me if you are sorting with a
> preorder (a partial order except antisymmetry is not required). For a
> partial order such a grouping is not so easy to define nor is it
> immedeately clear what it would mean.

Okay. I'll have to digest that one for a while.

> > It is interesting that we see list-of-sets emerging directly from the
> > nature of ordered data.
>
> Indeed, and let me add to this that there is already in fact some
> theory on pomsets (partially ordered multisets) as they are a natural
> generalization of sets, bags, lists and trees. The work is rather
> technical and not more than a first dip in the pool, but it might give
> you an idea of how theorists think about these things:
>
> http://citeseer.ist.psu.edu/grumbach95algebra.html

Looks interesting. 40 pages, wow.

My "inbox" of papers to read grows much faster than the outbox.

Marshall Received on Tue Mar 28 2006 - 05:14:03 CEST