Re: Idiomatic lisp - loops

"Tayssir John Gabbour" <tayssir.john@xxxxxxxxxxxxxx> writes:

On Mar 17, 4:29 am, Vassil Nikolov <vnikolov+use...@xxxxxxxxx> wrote:
On Fri, 16 Mar 2007 16:03:46 -0400, Raffael Cavallaro said:
| * (defun kv-insert (list elt)
| (stable-sort (push elt list) #'string< :key #'car))
^^^^

Apart from any efficiency considerations (this is O(n log n), while
it can be just O(n)), this either needs a (COPY-LIST LIST) or a
comment explaining why the value is expendable. Also, the PUSH is
gratuitous; this is a job for CONS.

You could have O(n) and non-destructiveness with:

(defun kv-insert (list elt)
(merge 'list (copy-seq list) (list elt) #'string< :key #'car))

This is the cleanest solution so far, I think. At least part of the
reason the original poster's code was longer, though, was that he
wanted to replace the value for a key if it was already in the list.
I don't know if this can be done without either an explicit iteration
or by making two passes, e.g.,

;; destructive
(defun kv-insert (list elt)
(let ((pair (assoc (car elt) list :test #'string=)))
(cond (pair
(setf (cdr pair) (cdr elt))
list)
(t (merge 'list list (list elt) #'string< :key #'car)))))
.

Relevant Pages

  • Re: Idiomatic lisp - loops
    ... So far I've got a recursive solution: ... (defun kv-insert (list elt) ... (let* ((h (car list)) ...
    (comp.lang.lisp)
  • Re: Idiomatic lisp - loops
    ... So far I've got a recursive solution: ... (defun kv-insert (list elt) ... (let* ((h (car list)) ... list) (list elt) ... ...
    (comp.lang.lisp)