From: netytan
Subject: Help with comparing lists.
Date: 
Message-ID: <1136100939.066709.131490@g47g2000cwa.googlegroups.com>
Hey all,

I'm working on a sort program just for fun, I'm new to lisp and I
thought it'd be a nice way to get to know it [by setting little tasks].

As part of this I need to be able to compare lists of items and decide
which list comes first. This is proving to be harder than I thought it
would be, I have my sorting program up to the point that I can express
the order single items are in but have no idea how to do this on lists
:).

Could someone maybe give me an example involving comparing two lists.
For obvious reasons this can't include the built-in function (sort).

I'm using CL but it shouldn't be a problem converting between other
dialects so please post some examples.

Thanks,

Mark.

From: Pascal Bourguignon
Subject: Re: Help with comparing lists.
Date: 
Message-ID: <87vex4z804.fsf@thalassa.informatimago.com>
"netytan" <·······@gmail.com> writes:
> I'm working on a sort program just for fun, I'm new to lisp and I
> thought it'd be a nice way to get to know it [by setting little tasks].
>
> As part of this I need to be able to compare lists of items and decide
> which list comes first. This is proving to be harder than I thought it
> would be, I have my sorting program up to the point that I can express
> the order single items are in but have no idea how to do this on lists
> :).
>
> Could someone maybe give me an example involving comparing two lists.
> For obvious reasons this can't include the built-in function (sort).
>
> I'm using CL but it shouldn't be a problem converting between other
> dialects so please post some examples.

Anything will do.  It's up to you to choose how you order your lists.


(defun measure (list)
  (if (atom list)
     (sxhash list)
     (+ (* MOST-POSITIVE-FIXNUM (measure (cdr list))) (sxhash (car list)))))

(defun list<= (a b) (<= (measure a) (measure b)))

(sort '((a) (b) (c) (d) (e) (f) (g h) (i j) (g l) (g n)) (function list<=))
--> ((F) (D) (E) (B) (C) (A) (G N) (G L) (I J) (G H))

(since SXHASH and MOST-POSITIVE-FIXNUM are implementation dependant,
this list<= is implementation dependant. You didn't specify anything
else).

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

"Specifications are for the weak and timid!"
From: Timofei Shatrov
Subject: Re: Help with comparing lists.
Date: 
Message-ID: <43b7a5a6.3204838@news.readfreenews.net>
On 31 Dec 2005 23:35:39 -0800, "netytan" <·······@gmail.com> tried to
confuse everyone with this message:

>Hey all,
>
>I'm working on a sort program just for fun, I'm new to lisp and I
>thought it'd be a nice way to get to know it [by setting little tasks].
>
>As part of this I need to be able to compare lists of items and decide
>which list comes first. This is proving to be harder than I thought it
>would be, I have my sorting program up to the point that I can express
>the order single items are in but have no idea how to do this on lists
>:).
>
>Could someone maybe give me an example involving comparing two lists.
>For obvious reasons this can't include the built-in function (sort).
>
>I'm using CL but it shouldn't be a problem converting between other
>dialects so please post some examples.

(defun list< (list1 list2)
"Compares two lists of integers by `alphabetic' order"
 (or (< (length list1) (length list2))
     (labels ((comp-list (L1 L2)
                 (and L1
                  (or (< (car L1) (car L2))
                      (and (= (car L1) (car L2)) 
                           (comp-list (cdr L1) (cdr L2)))))))
        (comp-list list1 list2))))

-- 
|a\o/r|,-------------.,---------- Timofei Shatrov aka Grue ------------.
| m"a ||FC AMKAR PERM|| mail: grue at mail.ru  http://grue3.tripod.com |
|  k  ||  PWNZ J00   || Kingdom of Loathing: Grue3 lvl 18 Seal Clubber |
`-----'`-------------'`-------------------------------------------[4*72]
From: Frank Buss
Subject: Re: Help with comparing lists.
Date: 
Message-ID: <mgk7z6gbq1w$.1xuzz4i3kyu91.dlg@40tude.net>
Timofei Shatrov wrote:

> (defun list< (list1 list2)
> "Compares two lists of integers by `alphabetic' order"

What do you mean by `alphabetic' order? When sorting alphabetic, then "xy"
is not less than "abcd", but with your function (list< '(5 6) '(1 2 3 4))
is t. The natural solution would be to implement something like string< for
lists with numbers:

(defun list< (list1 list2)
  (loop for i = 0 then (1+ i)
        for l1 = list1 then (cdr l1)
        for l2 = list2 then (cdr l2)
        for n1 = (car list1) then (car l1)
        for n2 = (car list2) then (car l2)
        until (and (null l1) (null l2))
        when (and (null n1) (not (null n2))) return i
        when (and (not (null n1)) (null n2)) return nil
        when (> n1 n2) return nil
        when (< n1 n2) return i))

(I'm sure there is a shorter recursive function)

Some test functions:

(defun list-to-string (list)
  (coerce (loop for i in list collect (code-char (+ (char-code #\a) i)))
          'string))

(defun test-eql (expected-result list1 list2)
  (let ((number-result (list< list1 list2))
        (string-result (string< (list-to-string list1)
                                (list-to-string list2))))
    (assert (and (eql number-result string-result)
                 (eql expected-result number-result)))))

(defun test ()
  (test-eql nil '() '())
  (test-eql nil '(1) '())
  (test-eql 0 '() '(1))
  (test-eql nil '(1) '(1))
  (test-eql nil '(2) '(1))
  (test-eql 0 '(1) '(2))
  (test-eql nil '(1 2) '(1 2))
  (test-eql 2 '(1 2) '(1 2 1))
  (test-eql nil '(1 2 1) '(1 2))
  (test-eql 1 '(1 2 3) '(1 3))
  (test-eql nil '(1 3) '(1 2 3)))

-- 
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Timofei Shatrov
Subject: Re: Help with comparing lists.
Date: 
Message-ID: <43b7d145.5210008@news.readfreenews.net>
On Sun, 1 Jan 2006 12:51:19 +0100, Frank Buss <··@frank-buss.de> tried
to confuse everyone with this message:

>Timofei Shatrov wrote:
>
>> (defun list< (list1 list2)
>> "Compares two lists of integers by `alphabetic' order"
>
>What do you mean by `alphabetic' order? When sorting alphabetic, then "xy"
>is not less than "abcd", but with your function (list< '(5 6) '(1 2 3 4))
>is t. 

Wow, I totally confused alphabetic order and comparison of numbers. My
algorithm seems to compare integer numbers in infinite (sufficiently
large) base.

-- 
|a\o/r|,-------------.,---------- Timofei Shatrov aka Grue ------------.
| m"a ||FC AMKAR PERM|| mail: grue at mail.ru  http://grue3.tripod.com |
|  k  ||  PWNZ J00   || Kingdom of Loathing: Grue3 lvl 18 Seal Clubber |
`-----'`-------------'`-------------------------------------------[4*72]
From: netytan
Subject: Re: Help with comparing lists.
Date: 
Message-ID: <1136170266.665115.138100@g49g2000cwa.googlegroups.com>
Thanks a lot guys, this is what I came up with. I'm sure it can be done
better but I can't see a way right now :). Maybe i will in the future

(defun list< (x y set)
  (and (listp x)
       (listp y)

      (let ((pos-x (position (car x) set))
	    (pos-y (position (car y) set)))

	(or (< pos-x pos-y)
            (and (= pos-x pos-y)
	        (if (and (cdr x) (cdr y))
	          (list< (cdr x) (cdr y) set) t))))))

Thanks again,

Mark.
From: Gareth McCaughan
Subject: Re: Help with comparing lists.
Date: 
Message-ID: <87vex27p97.fsf@g.mccaughan.ntlworld.com>
Timofei Shatrov wrote:

> Wow, I totally confused alphabetic order and comparison of numbers. My
> algorithm seems to compare integer numbers in infinite (sufficiently
> large) base.

The word you're looking for is "lexicographic". :-)

-- 
Gareth McCaughan
.sig under construc
From: Pascal Bourguignon
Subject: Re: Help with comparing lists.
Date: 
Message-ID: <87d5jcywf1.fsf@thalassa.informatimago.com>
"netytan" <·······@gmail.com> writes:

> Hey all,
>
> I'm working on a sort program just for fun, I'm new to lisp and I
> thought it'd be a nice way to get to know it [by setting little tasks].
>
> As part of this I need to be able to compare lists of items and decide
> which list comes first. This is proving to be harder than I thought it
> would be, I have my sorting program up to the point that I can express
> the order single items are in but have no idea how to do this on lists
> :).
>
> Could someone maybe give me an example involving comparing two lists.
> For obvious reasons this can't include the built-in function (sort).
>
> I'm using CL but it shouldn't be a problem converting between other
> dialects so please post some examples.

A quick and dirty solution that's rather portable is:

  (string<= (write-to-string l1 :circle t :readably nil
               :array t :base 10 :radix nil :case :upcase :escape t :gensym t
               :length nil :level nil :lines nil :miser-width nil :pretty nil)
            (write-to-string l2 :circle t :readably nil
               :array t :base 10 :radix nil :case :upcase :escape t :gensym t
               :length nil :level nil :lines nil :miser-width nil :pretty nil))

(or quicker and dirtier:
     (string<= (format nil "~S" l1) (format nil "~S" l2))
)

The only case where you may get different results in different
implementations is when the lists contain items that are not printable
readably.

Also, in some implementations after a garbage collection, these items
not printable readably may change of order, (in this case, the sxhash
based solution is better).

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
I need a new toy.
Tail of black dog keeps good time.
Pounce! Good dog! Good dog!