lexicographic list comparison

lexicographic list comparison

[Sam Steingold]

Hi,

What do you do when sorting a list of lists of numbers?

There does not appear to be a standard comparison function like
--8<---------------cut here---------------start------------->8---
(defun lexicographic-compare-lists (l1 l2 &optional lessp)
  "lexicographic list comparison"
  (unless lessp
    (setq lessp #'<))
  (or (null l2) (null l1)
      (funcall lessp (car l1) (car l2))
      (and (not (funcall lessp (car l2) (car l1)))
           (lexicographic-compare-lists (cdr l1) (cdr l2) lessp))))
--8<---------------cut here---------------end--------------->8---

[[[It appears that it is less critical for strings because one can do
--8<---------------cut here---------------start------------->8---
(sort list-of-lists-of-strings
      (lambda (l1 l2) (string< (string-join l1) (string-join l2))))
--8<---------------cut here---------------end--------------->8---
instead of
--8<---------------cut here---------------start------------->8---
(sort list-of-lists-of-strings
      (lambda (l1 l2) (lexicographic-compare-lists l1 l2 #'string<)))
--8<---------------cut here---------------end--------------->8---
even though it conses for each comparison(!)]]]

Or maybe sorting lists of lists is just such a rare op that no one has
ever encountered it before me? ;-)

Thank you.

-- 
Sam Steingold (https://aphar.dreamwidth.org/) on darwin Ns 10.3.2113
https://lastingimpactpsychology.com https://steingoldpsychology.com
https://ij.org/ https://honestreporting.com https://memri.org
You do not have time or money to sue anyone rich enough to be worth suing.

Re: lexicographic list comparison

[Mattias Engdegård]

9 sep. 2022 kl. 21.27 skrev Sam Steingold <sds@gnu.org>:

> What do you do when sorting a list of lists of numbers?

Sigh deeply and write ad-hoc code for the nth time.

> Or maybe sorting lists of lists is just such a rare op that no one has
> ever encountered it before me?

It would be useful to have a total ordering on Lisp values: for heterogeneous ordered collections, for simplifying multi-key sorting, for normalising unordered collections, etc.

The devil is in the details: are strings compared with our without properties? Do we observe the wonky IEEE rules for ordering floats? Is there a particularly useful ordering between elements of different types? Do we need to worry about circularity? How do we compare hash tables? And so on.

Consistency with `equal` would be desirable (up to hash table identity, perhaps).

Re: lexicographic list comparison

[Emanuel Berg]

Mattias Engdegård wrote:

>> Or maybe sorting lists of lists is just such a rare op that
>> no one has ever encountered it before me?
>
> It would be useful to have a total ordering on Lisp values:
> for heterogeneous ordered collections, for simplifying
> multi-key sorting, for normalising unordered
> collections, etc.
>
> The devil is in the details: are strings compared with our
> without properties? Do we observe the wonky IEEE rules for
> ordering floats? Is there a particularly useful ordering
> between elements of different types? Do we need to worry
> about circularity? How do we compare hash tables? And so on.
>
> Consistency with `equal` would be desirable (up to hash
> table identity, perhaps).

Interesting, what is this, type theory?

Sounds like something that is available in Haskell maybe ...

What is the benefit if you have it? Sort things recursively
and with no fear running into data of a type that would
wreck it?

It's easy to do, (order-pair a b) which accepts any an all
data and returns the list (a b) iff a < b. It could first
check types, then delegate the task to the existing
greater-than function for all cases that ... makes sense.

Making up rules that makes sense for everything that don't
make sense to compare is maybe more difficult ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: lexicographic list comparison

[tomas]

[-- Attachment #1: Type: text/plain, Size: 1109 bytes --]

On Sat, Sep 10, 2022 at 11:07:49AM +0200, Mattias Engdegård wrote:
> 9 sep. 2022 kl. 21.27 skrev Sam Steingold <sds@gnu.org>:
> 
> > What do you do when sorting a list of lists of numbers?
> 
> Sigh deeply and write ad-hoc code for the nth time.

:-)

> It would be useful to have a total ordering on Lisp values: for heterogeneous ordered collections, for simplifying multi-key sorting, for normalising unordered collections, etc.
> 
> The devil is in the details: are strings compared with our without properties? Do we observe the wonky IEEE rules for ordering floats? Is there a particularly useful ordering between elements of different types? Do we need to worry about circularity? How do we compare hash tables? And so on.
> 

And language-dependent collation, and Unicode equivalence, and NaNs
and...

Details, indeed :-)

A look at the troubles and tribulations a DBMS goes through gives one
a rough idea on how interesting a general solution can become...

> Consistency with `equal` would be desirable (up to hash table identity, perhaps).

This, too :)

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: lexicographic list comparison

[Sam Steingold]

> * Mattias Engdegård <znggvnfr@npz.bet> [2022-09-10 11:07:49 +0200]:
>
> 9 sep. 2022 kl. 21.27 skrev Sam Steingold <sds@gnu.org>:
>
>> What do you do when sorting a list of lists of numbers?
>
> Sigh deeply and write ad-hoc code for the nth time.

okay, so, I suppose, you find the `lexicographic-compare-lists' from TS
useful, right?

>> Or maybe sorting lists of lists is just such a rare op that no one has
>> ever encountered it before me?
>
> It would be useful to have a total ordering on Lisp values: for
> heterogeneous ordered collections, for simplifying multi-key sorting,
> for normalising unordered collections, etc.

I certainly have no intention of comparing strings with numbers &c.
My question was about a list of _homogeneous_ lists, and comparing to,
say, lists of numbers, is done lexicographically based on number
comparison.


-- 
Sam Steingold (https://aphar.dreamwidth.org/) on darwin Ns 10.3.2113
https://lastingimpactpsychology.com https://steingoldpsychology.com
https://www.peaceandtolerance.org/ https://www.memritv.org
When C++ is your hammer, everything looks like a thumb.

Re: lexicographic list comparison

[mattiase]

12 sep. 2022 kl. 16.45 skrev Sam Steingold <sds@gnu.org>:

> okay, so, I suppose, you find the `lexicographic-compare-lists' from TS
> useful, right?

(What is TS in this context?)
I usually just copy-paste code from an older project of mine (who doesn't?) because that way I know that it works, how it works, what its performance is like, etc.

> I certainly have no intention of comparing strings with numbers &c.
> My question was about a list of _homogeneous_ lists, and comparing to,
> say, lists of numbers, is done lexicographically based on number
> comparison.

We could certainly add comparison functions for lists, then ones for arrays, then for hash tables, and so on. Or just write one that works for all built-in types and impose an ordering between objects of distinct types. It would be more useful (if harder to write).

Re: lexicographic list comparison

[Stefan Monnier]

>> I certainly have no intention of comparing strings with numbers &c.
>> My question was about a list of _homogeneous_ lists, and comparing to,
>> say, lists of numbers, is done lexicographically based on number
>> comparison.
>
> We could certainly add comparison functions for lists, then ones for arrays,
> then for hash tables, and so on. Or just write one that works for all
> built-in types and impose an ordering between objects of distinct types. It
> would be more useful (if harder to write).

We could write a `cl-defgeneric` with a few basic instances.

Another option is to provide combinators: e.g. provide a `list-compare`
function which takes the comparison function to use for the elements and
return a comparison function that works of lists of such elements, so
you can do things like:

    (sort foo (list-compare (list-compare #'<)))

[ Tho I suspect you'll want those comparison functions to return
  a -1/0/1 result rather than just a boolean, so you'd need an extra
  combinator to turn such a comparison function into the kind expected
  by `sort`.  ]


-- Stefan

Re: lexicographic list comparison

[Sam Steingold]

> *  <znggvnfr@npz.bet> [2022-09-12 19:53:42 +0200]:
>
> 12 sep. 2022 kl. 16.45 skrev Sam Steingold <sds@gnu.org>:
>
>> okay, so, I suppose, you find the `lexicographic-compare-lists' from TS
>> useful, right?
>
> (What is TS in this context?)

TS=topic start (the initial message in the thread)

> I usually just copy-paste code from an older project of mine (who
> doesn't?) because that way I know that it works, how it works, what
> its performance is like, etc.

I abhor code copying.
If I find that I reuse a function, I put it into a library.

>> I certainly have no intention of comparing strings with numbers &c.
>> My question was about a list of _homogeneous_ lists, and comparing to,
>> say, lists of numbers, is done lexicographically based on number
>> comparison.
>
> We could certainly add comparison functions for lists, then ones for
> arrays,

nah, all sequences are compared the same way.

> then for hash tables, and so on.
> Or just write one that works for all built-in types and impose an
> ordering between objects of distinct types. It would be more useful
> (if harder to write).

I seriously doubt this could be useful.

-- 
Sam Steingold (https://aphar.dreamwidth.org/) on darwin Ns 10.3.2113
https://lastingimpactpsychology.com https://steingoldpsychology.com
https://iris.org.il https://ij.org/ https://jij.org https://camera.org
Calculus has its limits.

Re: lexicographic list comparison

[Sam Steingold]

> * Stefan Monnier <zbaavre@veb.hzbagerny.pn> [2022-09-12 14:31:33 -0400]:
>
> [ Tho I suspect you'll want those comparison functions to return
>   a -1/0/1 result rather than just a boolean, so you'd need an extra
>   combinator to turn such a comparison function into the kind expected
>   by `sort`.  ]

The predicate argument to lisp sort returns a boolean.

-- 
Sam Steingold (https://aphar.dreamwidth.org/) on darwin Ns 10.3.2113
https://lastingimpactpsychology.com https://steingoldpsychology.com
https://jihadwatch.org https://www.dhimmitude.org https://iris.org.il
You won't get smarter by calling me a fool.

Re: lexicographic list comparison

[Stefan Monnier]

Sam Steingold [2022-09-12 14:41:47] wrote:
>> * Stefan Monnier <zbaavre@veb.hzbagerny.pn> [2022-09-12 14:31:33 -0400]:
>> [ Tho I suspect you'll want those comparison functions to return
>>   a -1/0/1 result rather than just a boolean, so you'd need an extra
>>   combinator to turn such a comparison function into the kind expected
>>   by `sort`.  ]
>
> The predicate argument to lisp sort returns a boolean.

Indeed, but `list-compare` will likely want the other kind, hence the
need for combinators that change from kind to the other.


        Stefan