[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: How to delete all nil properties from a plist?

From: Pascal J. Bourguignon
Subject: Re: How to delete all nil properties from a plist?
Date: Thu, 06 Aug 2015 04:32:09 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)

Emanuel Berg <address@hidden> writes:

> "Pascal J. Bourguignon" <address@hidden>
> writes:
>> Nonetheless, if you find it would be useful to have
>> such a list, you can establish it.
>> There are 636 functions in CL.
>> If you research the best algorithms for each, noting
>> the time and space complexities, and finding what
>> complexities and (approximate) actual factors each
>> implementation provide, for 2 functions each day,
>> you will be done in less than a year.
> You don't have to have a list of every single
> function, the most common will do - but of course, the
> more complete the list, the better...
> But how do you find out? Before you told me, I didn't
> know `append' was linear. Do you examine the code and
> do analysis? If so, I'll pass this project :)

Why would you pass, reading the source of an implementation is one of
the most instructive things you can do as a programmer.

Indeed, reading the sources of APPEND, and even, comparing it across
several implementation would let you learn a lot.

The alternative course, is not to read an implementation, but to write
an implementation yourself!

You read the clhs:

    append &rest lists => result

    Arguments and Values:

    list---each must be a proper list except the last, which may be any

    result---an object. This will be a list unless the last list was not a
    list and all preceding lists were null.


    append returns a new list that is the concatenation of the copies. lists
    are left unchanged; the list structure of each of lists except the last
    is copied. The last argument is not copied; it becomes the cdr of the
    final dotted pair of the concatenation of the preceding lists, or is
    returned directly if there are no preceding non-empty lists.

and you implement it.

So, let's see, the last list must not be copied, but taken as is for the
result. Then we must copy the other lists, and concatenate them.

(shadow 'append)

(defun append (&rest lists)
  (when lists
    (let* ((lists (reverse lists))
           (result (pop lists)))
      (dolist (list lists result)
        (setf result (nconc (copy-list list) result))))))

This is clearly O(n), with n = (reduce 'length (butlast lists)),
since we call copy-list on all lists but the last, copy-list is
O(length(list)), and nconc which is also O(length(list))
so our function is O(Σ(2*length(list))), summing over all the lists but
the last one, = O(reduce 'length (butlast lists))

But if you implement it yourself, 

1- you won't learn the same,

2- you'll always have a doubt whether you've found the most efficient
   algorithm, (unless you can prove no algorithm can be more efficient
   than yours),

3- you might make an error,

4- you won't learn the various implementation techniques used in the

Come on, it's not hard, just type M-. and eg. on ccl you get:

(defun append (&rest lists)
  (declare (dynamic-extent lists))
  "Construct a new list by concatenating the list arguments"
  (if lists
    (let* ((head (cons nil nil))
           (tail head))
      (declare (dynamic-extent head)
               (cons head tail))
      (do* ()
           ((null lists) (cdr head))
        (let* ((list (pop lists)))
          (if (null lists)
            (rplacd tail list)
            (dolist (element list)
                (setq tail (cdr (rplacd tail (cons element nil)))))))))))

and on sbcl you get:

(defun append (&rest lists)
  "Construct a new list by concatenating the list arguments"
  (declare (truly-dynamic-extent lists) (optimize speed))
  (labels ((fail (object)
             (error 'type-error
                    :datum object
                    :expected-type 'list))
           (append-into (last-cons current rest)
             ;; Set (CDR LAST-CONS) to (APPLY #'APPEND CURRENT REST).
             (declare (cons last-cons rest))
             (if (listp current)
                 (if (consp current)
                     ;; normal case, cdr down the list
                     (append-into (setf (cdr last-cons) (list (car current)))
                                  (cdr current)
                     ;; empty list
                     (let ((more (cdr rest)))
                       (if (null more)
                           (setf (cdr last-cons) (car rest))
                           (append-into last-cons (car rest) more))))
                 (fail current)))
           (append1 (lists)
             (let ((current (car lists))
                   (rest (cdr lists)))
               (cond ((null rest)
                     ((consp current)
                      (let ((result (truly-the cons (list (car current)))))
                        (append-into result
                                     (cdr current)
                     ((null current)
                      (append1 rest))
                      (fail current))))))
    (append1 lists)))

and also, you get a compiler-macros for append, which you should have
a look at, since it actually use a different function in some cases.

and for clisp you get:

{ /* (APPEND {list}), CLTL p. 268 */
  if (argcount==0) {
    VALUES1(NIL); /* no arguments -> return NIL as result */
  } else {
    /* Append arguments. Run the loop argcount-1 times: */
    while (--argcount) {
      /* STACK_0 = result list from right. */
      /* STACK_1 := (append STACK_1 STACK_0), increase STACK by 1: */
      var object list1;
        var object list2 = popSTACK(); /* result list (from right) */
        list1 = STACK_0; /* Argument to be added to the front */
        STACK_0 = list2; /* stack resulting list */
      /* list1 needs to be a list: */
      if (atomp(list1))
        if (nullp(list1))
          ; /* if list1=NIL: (append nil x) = x, do nothing */
      else {
        /* (append list1 STACK_0), and list1 is a Cons: */
        /* Copy list1 and keep last Cons: */
        var object run;
          var object new_list = allocate_cons();
          run = STACK_0; /* run runs through the old list list1 */
          Car(new_list) = Car(run);
          STACK_0 = new_list;
        /* Loop: STACK_1 has the full copy, STACK_0 = LAST of it, */
        /* run = the corresponding Cons of the original list list1. */
        while ( run=Cdr(run), !endp(run) ) {
          /* one more Cons */
          pushSTACK(run); /* save run */
          var object new_cons = allocate_cons(); /* allocate new Cons */
          run = popSTACK(); /* put back run */
          Cdr(STACK_0) = new_cons; /* and add as CDR of the LAST */
          Car(new_cons) = Car(run); /* copy CAR */
          STACK_0 = new_cons; /* this is now the new LAST */
        /* Copy ready. STACK_2 = current result list, */
        /* STACK_1 = copy of list1, STACK_0 = LAST of it. */
        run = popSTACK(); /* end of copy */
        list1 = popSTACK(); /* copy finished */
        /*if (!nullp(Cdr(run))) ????
        Cdr(run) = STACK_0; /* add result copy */
        STACK_0 = list1; /* and the is the new result list */
    VALUES1(popSTACK()); /* result list as value */

and in ecl:

static cl_object *
append_into(cl_object head, cl_object *tail, cl_object l)
        if (!Null(*tail)) {
                /* (APPEND '(1 . 2) 3) */
        while (CONSP(l)) {
                cl_object cons = ecl_list1(ECL_CONS_CAR(l));
                *tail = cons;
                tail = &ECL_CONS_CDR(cons);
                l = ECL_CONS_CDR(l);
        *tail = l;
        return tail;

@(defun append (&rest rest)
        cl_object head = ECL_NIL, *tail = &head;
        for (; narg > 1; narg--) {
                cl_object other = ecl_va_arg(rest);
                tail = append_into(head, tail, other);
        if (narg) {
                if (!Null(*tail)) {
                        /* (APPEND '(1 . 2) 3) */
                *tail = ecl_va_arg(rest);
        @(return head)

__Pascal Bourguignon__       
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

reply via email to

[Prev in Thread] Current Thread [Next in Thread]