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.
"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!"
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]
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
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]
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.
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
"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!