What is the simpliest, most elegant way to insert a symbol into an
ordered list of symbols? For example, say I have the list
'(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
But also so that inserting a duplicate, like 2 won't result in
duplicate entries?
I won't embarrass myself to the ridicule that would ensue if I showed
the horrors I've come up with (they do work, but they're butt-ugly).
Jeff Cunningham wrote:
> What is the simpliest, most elegant way to insert a symbol into an
> ordered list of symbols? For example, say I have the list
>
> '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
>
> But also so that inserting a duplicate, like 2 won't result in
> duplicate entries?
>
> I won't embarrass myself to the ridicule that would ensue if I showed
> the horrors I've come up with (they do work, but they're butt-ugly).
Maybe something using MERGE and REMOVE-DUPLICATES? That would combine
into a 1 or 2 liner.
Tayssir
--
SNL Conspiracy Theory Rock video:
http://www.milkandcookies.com/links/29719/details/
On Fri, 30 Sep 2005 20:56:38 -0700, Tayssir John Gabbour wrote:
> Jeff Cunningham wrote:
>> What is the simpliest, most elegant way to insert a symbol into an
>> ordered list of symbols? For example, say I have the list
>>
>> '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
>>
>> But also so that inserting a duplicate, like 2 won't result in
>> duplicate entries?
>>
>> I won't embarrass myself to the ridicule that would ensue if I showed
>> the horrors I've come up with (they do work, but they're butt-ugly).
>
> Maybe something using MERGE and REMOVE-DUPLICATES? That would combine
> into a 1 or 2 liner.
>
> Tayssir
Hey - I like that idea. Its better than my best (push followed by sort). I
could probably save work by doing a member test and only merging if not a
member.
-jeff
Jeff Cunningham <·······@cunningham.net> writes:
> What is the simpliest, most elegant way to insert a symbol into an
> ordered list of symbols? For example, say I have the list
>
> '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
Uh, those are numbers, not symbols. Regardless, this will work for
objects:
(defun ordered-insert (object ordered-set &key (predicate #'<) (test #'eql))
(labels ((insert (acc set)
(cond ((or (null set)
(funcall test object (car set)))
(nreconc acc set))
((funcall predicate object (car set))
(nreconc (cons object acc) set))
(t (insert (cons (car set) acc) (cdr set))))))
(insert () ordered-set)))
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
On Sat, 01 Oct 2005 01:04:22 -0700, Thomas F. Burdick wrote:
> ···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
>> Jeff Cunningham <·······@cunningham.net> writes:
>>
>> > What is the simpliest, most elegant way to insert a symbol into an
>> > ordered list of symbols? For example, say I have the list
>> >
>> > '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
>>
>> Uh, those are numbers, not symbols. Regardless, this will work for
>> objects:
>>
Those are examples, not numbers. ;)
-jeff
In article <······························@cunningham.net>,
Jeff Cunningham <·······@cunningham.net> wrote:
> What is the simpliest, most elegant way to insert a symbol into an
> ordered list of symbols? For example, say I have the list
>
> '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
>
> But also so that inserting a duplicate, like 2 won't result in
> duplicate entries?
>
> I won't embarrass myself to the ridicule that would ensue if I showed
> the horrors I've come up with (they do work, but they're butt-ugly).
(setq list (sort (pushnew 4 list)))
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
On Sat, 01 Oct 2005 02:19:14 -0700, Djamel wrote:
> Hello, I'm new to Lisp, so it might be not written in good Lisp style.
> CL-USER> (remove-duplicates (sort (cons 4 '(1 2 6 7)) '<))
>
> (1 2 4 6 7)
> CL-USER> (remove-duplicates (sort (cons 4 '(1 2 4 6 7)) '<))
>
> (1 2 4 6 7)
> CL-USER> (defun add-number-to-list (num lst)
>
> (if
>
> (and
>
> (numberp num)
>
> (listp lst))
>
> (remove-duplicates (sort (cons num lst) '<))))
>
>
>
That works for numbers, but the numbers were only examples of what could
be objects: like trying to insert 'c in the list '(a b d e).
-jeff
Jeff Cunningham wrote:
> What is the simpliest, most elegant way to insert a symbol into an
> ordered list of symbols? For example, say I have the list
>
> '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
>
> But also so that inserting a duplicate, like 2 won't result in
> duplicate entries?
>
> I won't embarrass myself to the ridicule that would ensue if I showed
> the horrors I've come up with (they do work, but they're butt-ugly).
>
Simplest (maybe)
(defun insert-sorted (item list)
(if (member item list :test #'=)
list
(sort (cons item list) #'<)))
Wade
Jeff Cunningham <·······@cunningham.net> writes:
> What is the simpliest, most elegant way to insert a symbol into an
> ordered list of symbols? For example, say I have the list
>
> '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
>
> But also so that inserting a duplicate, like 2 won't result in
> duplicate entries?
>
> I won't embarrass myself to the ridicule that would ensue if I showed
> the horrors I've come up with (they do work, but they're butt-ugly).
If you didn't mind the order, you could use pushnew:
(defparameter bag (list 'one 2 :three))
(pushnew "IV" bag)
bag --> ("IV" one 2 :three)
If you mind the order and want to insert new items, why do you use a list?
A binary tree would be better!
Inserting a new item in a list is easy: you just need to keep a
reference to the previous cons.
(defun insert-in-order (item list le &key (key (function identity)))
"destructively insert the item into the list according to the order LE."
(let ((item-key (funcall key item)))
(flet ((item-less? (other)
(and (funcall le item-key (funcall key other))
(not (funcall le (funcall key other) item-key))))
(item-equal? (other)
(and
(funcall le (funcall key other) item-key)
(funcall le item-key (funcall key other))))
(item-greater? (other)
(and (funcall le (funcall key other) item-key)
(not (funcall le item-key (funcall key other))))))
(cond
((null list) (list item))
((item-less? (car list)) (cons item list))
((item-equal? (car list)) list)
(t (loop
:for previous = list then current
:for current = (cdr previous)
:while (and current (item-greater? (car current)))
:finally (progn
(cond
((null current) (setf (cdr previous) (cons item nil)))
((item-equal? (car current)))
(t (setf (cdr previous) (cons item (cdr previous)))))
(return list))))))))
(dolist (test '(
((:a)
(let ((list (list)))
(setf list (insert-in-order :a list (function string<=)))
list))
((:a :b :c)
(let ((list (list :b :c)))
(setf list (insert-in-order :a list (function string<=)))
list))
((:a :b :c)
(let ((list (list :a :b :c)))
(setf list (insert-in-order :a list (function string<=)))
list))
((:a :b :c)
(let ((list (list :a :c)))
(setf list (insert-in-order :b list (function string<=)))
list))
((:a :b :c)
(let ((list (list :a :b)))
(setf list (insert-in-order :c list (function string<=)))
list))
))
(assert (equal (first test) (eval (second test)))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner
On Sat, 01 Oct 2005 06:40:57 +0200, Pascal Bourguignon wrote:
>
> If you mind the order and want to insert new items, why do you use a list?
> A binary tree would be better!
I'm liking your suggestion more all the time. It would involve rewriting
some other code but might result in a better product.
-jeff
Jeff Cunningham <·······@cunningham.net> writes:
>> If you mind the order and want to insert new items, why do you use a list?
>> A binary tree would be better!
>
>
> I'm liking your suggestion more all the time. It would involve rewriting
> some other code but might result in a better product.
Indeed. Note that while (setf list (sort (pushnew item list) lessp))
is short and clean, it's good only for one-shoots, prototypes, or
short lists. In other case, you get O(n�) (we're in worst case for
quicksort; what algorithm does your implementation use?) or
O(n�log(n)) if heapsort is used, while the normal search and insert is
O(n). A binary tree will be O(log(n)).
--
__Pascal Bourguignon__ http://www.informatimago.com/
I need a new toy.
Tail of black dog keeps good time.
Pounce! Good dog! Good dog!
In article <··············@thalassa.informatimago.com>,
Pascal Bourguignon <····@mouse-potato.com> wrote:
> Jeff Cunningham <·······@cunningham.net> writes:
> >> If you mind the order and want to insert new items, why do you use a list?
> >> A binary tree would be better!
> >
> >
> > I'm liking your suggestion more all the time. It would involve rewriting
> > some other code but might result in a better product.
>
> Indeed. Note that while (setf list (sort (pushnew item list) lessp))
> is short and clean, it's good only for one-shoots, prototypes, or
> short lists. In other case, you get O(n�) (we're in worst case for
> quicksort; what algorithm does your implementation use?) or
> O(n�log(n)) if heapsort is used, while the normal search and insert is
> O(n). A binary tree will be O(log(n)).
If you know that the integers are going to be small you can use a bit
vector representation. Then inserts (and deletes) are O(1).
rg
Pascal Bourguignon wrote:
> Inserting a new item in a list is easy: you just need to keep a
> reference to the previous cons.
[much code]
wow, this looks complicated. Do you really need item-equal and item-greater
when you have item-less?
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> Pascal Bourguignon wrote:
>
>> Inserting a new item in a list is easy: you just need to keep a
>> reference to the previous cons.
>
> [much code]
>
> wow, this looks complicated. Do you really need item-equal and item-greater
> when you have item-less?
item-equal? is needed to avoid duplicates.
And there's some optimization going on: computing the key for the item once.
(Some more could come in to avoid computing several times the key for
the current item).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
Pascal Bourguignon wrote:
> item-equal? is needed to avoid duplicates.
if it is not less than, it is equal or it is greater than, so all you need
is less than, which you need for a sorted list anyway.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> (when (and (< before item) (not after))
> (setf (cdr sublist) (list item))
> (loop-finish))
> (when (and (< before item) (< item after))
> (let ((new-cons (cons item (cdr sublist))))
> (setf (cdr sublist) new-cons)
> (loop-finish))))))))
code duplication smells :-) , this is more Lispy and 4 lines shorter:
(defun insert (item list)
(let ((first (car list)))
(if (or (not first) (< item first))
(cons item list)
(loop for sublist on list finally (return list) do
(let ((before (car sublist))
(after (cadr sublist)))
(when (and (< before item)
(or (not after) (< item after)))
(setf (cdr sublist) (cons item (cdr sublist)))
(loop-finish)))))))
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Emilio Lopes
Subject: Re: Looking for a simple elegant solution
Date:
Message-ID: <srek74w0d0.fsf@tiscali.de>
Jeff Cunningham writes:
> What is the simpliest, most elegant way to insert a symbol into an
> ordered list of symbols? For example, say I have the list
> '(1 2 6 7) and I want to insert 4 so it ends up '(1 2 4 6 7).
> But also so that inserting a duplicate, like 2 won't result in
> duplicate entries?
Simple and elegant, but not constant in space. This is easy to change
if keep state in another variable.
Extending the following to work with types other than numbers is left
as an exercise for the reader.
This is SBCL 0.8.16, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun ordered-insert (n lst)
(cond ((null lst) (list n))
((< n (car lst)) (cons n lst))
((= n (car lst)) lst)
((> n (car lst))
(cons (car lst) (ordered-insert n (cdr lst))))))
ORDERED-INSERT
* (ordered-insert -5 '(1 2 6 7))
(-5 1 2 6 7)
* (ordered-insert 4 '(1 2 6 7))
(1 2 4 6 7)
* (ordered-insert 42 '(1 2 6 7))
(1 2 6 7 42)
* (ordered-insert 6 '(1 2 6 7))
(1 2 6 7)
* (ordered-insert 1 '(1 2 6 7))
(1 2 6 7)