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

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

[Pascal J. Bourguignon]

Marcin Borkowski <mbork@mbork.pl> writes:

> Hi all,
>
> so I'm still using plists, though I'm less and less sure that they are
> actually better than alists for my use-case.  Now I need to delete all
> properties whose value is nil.  I'm using this function:
>
> (defun plist-clear (plist)
>   "Return PLIST with all nil properties deleted."
>   (cond
>    ((< (length plist) 2) nil)

very bad, you walk the list once more.

>    ((null (cadr plist)) (cddr plist))

ok.

>    (t (cons (car plist) (cons (cadr plist) (plist-clear (cddr
>    plist)))))))

And since you call plist-clear recursive, the above walk makes it O(n²)!


> Question 1: is there a better way to write it?  (Especially the last
> line.)

Yes.

(defun plist-clear (plist)
  "Return PLIST with all nil properties deleted."
  (loop for (k v) on plist by (function cddr)
        when v
        collect k collect v))
 
> Question 2: how would I do the analogous thing with alists?

(defun alist-clear (alist)
  "Return ALIST with all nil properties deleted."
  (remove* nil alist :key (function cdr)))


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

How to delete all nil properties from a plist?

[Marcin Borkowski]

Hi all,

so I'm still using plists, though I'm less and less sure that they are
actually better than alists for my use-case.  Now I need to delete all
properties whose value is nil.  I'm using this function:

--8<---------------cut here---------------start------------->8---
(defun plist-clear (plist)
  "Return PLIST with all nil properties deleted."
  (cond
   ((< (length plist) 2) nil)
   ((null (cadr plist)) (cddr plist))
   (t (cons (car plist) (cons (cadr plist) (plist-clear (cddr plist)))))))
--8<---------------cut here---------------end--------------->8---

Question 1: is there a better way to write it?  (Especially the last
line.)

Question 2: how would I do the analogous thing with alists?

TIA,

-- 
Marcin Borkowski
http://octd.wmi.amu.edu.pl/en/Marcin_Borkowski
Faculty of Mathematics and Computer Science
Adam Mickiewicz University

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

[Marcin Borkowski]

On 2015-08-02, at 00:03, Marcin Borkowski <mbork@mbork.pl> wrote:

> Hi all,
>
> so I'm still using plists, though I'm less and less sure that they are
> actually better than alists for my use-case.  Now I need to delete all
> properties whose value is nil.  I'm using this function:
>
> --8<---------------cut here---------------start------------->8---
> (defun plist-clear (plist)
>   "Return PLIST with all nil properties deleted."
>   (cond
>    ((< (length plist) 2) nil)
>    ((null (cadr plist)) (cddr plist))
>    (t (cons (car plist) (cons (cadr plist) (plist-clear (cddr plist)))))))
> --8<---------------cut here---------------end--------------->8---
>
> Question 1: is there a better way to write it?  (Especially the last
> line.)
>
> Question 2: how would I do the analogous thing with alists?

OK, so what about this?  Is there a better way (which would probably
mean, is such function already defined)?

--8<---------------cut here---------------start------------->8---
(defun alist-clear (alist)
  "Return ALIST with all pairs with nil value deleted."
  (if alist
      (if (cdar alist)
	  (cons (car alist)
		(alist-clear (cdr alist)))
	(alist-clear (cdr alist)))))
--8<---------------cut here---------------end--------------->8---

TIA,

-- 
Marcin Borkowski
http://octd.wmi.amu.edu.pl/en/Marcin_Borkowski
Faculty of Mathematics and Computer Science
Adam Mickiewicz University

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

[Emanuel Berg]

Marcin Borkowski <mbork@mbork.pl> writes:

>> Hi all, so I'm still using plists, though I'm less
>> and less sure that they are actually better than
>> alists for my use-case. Now I need to delete all
>> properties whose value is nil. I'm using this
>> function:

Try this:

(require 'cl)

(defun plist-drop-nil-props (l)
  (let((new)
       (prop nil) )
    (cl-loop for x in l
             do (if (or (setq prop (not prop)) x)
                    (setq new (append new (list x)))
                  (setq new (butlast new))))
    new))

(plist-drop-nil-props
 '(nil nil a 1 b 2 c nil d nil e 5 g nil nil nil) ) ; (a 1 b 2 e 5)

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> Marcin Borkowski <mbork@mbork.pl> writes:
>
>>> Hi all, so I'm still using plists, though I'm less
>>> and less sure that they are actually better than
>>> alists for my use-case. Now I need to delete all
>>> properties whose value is nil. I'm using this
>>> function:
>
> Try this:
>
> (require 'cl)
>
> (defun plist-drop-nil-props (l)
>   (let((new)
>        (prop nil) )
>     (cl-loop for x in l
>              do (if (or (setq prop (not prop)) x)
>                     (setq new (append new (list x)))
>                   (setq new (butlast new))))
>     new))

This is horrible. Again, you can't prevent yourself writing O(n²) code
when O(n) would do perfectly.




-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> This is horrible. Again, you can't prevent yourself
> writing O(n²) code when O(n) would do perfectly.

Is it `append' or `butlast' that is linear as well?

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Rusi]

On Sunday, August 2, 2015 at 7:06:24 AM UTC+5:30, Pascal J. Bourguignon wrote:
> Emanuel Berg writes:
> 
> > Marcin Borkowski writes:
> >
> >>> Hi all, so I'm still using plists, though I'm less
> >>> and less sure that they are actually better than
> >>> alists for my use-case. Now I need to delete all
> >>> properties whose value is nil. I'm using this
> >>> function:
> >
> > Try this:
> >
> > (require 'cl)
> >
> > (defun plist-drop-nil-props (l)
> >   (let((new)
> >        (prop nil) )
> >     (cl-loop for x in l
> >              do (if (or (setq prop (not prop)) x)
> >                     (setq new (append new (list x)))
> >                   (setq new (butlast new))))
> >     new))
> 
> This is horrible. Again, you can't prevent yourself writing O(n²) code
> when O(n) would do perfectly.

Hey Pascal!
If O(n²) is 'horrible' what is O(n³)? And O(n⁴) ?
And the stuff in NP?
[I suppose the french lexicon has many adjectives...]

BTW: Thanks for being civilized/cultured and using a non-ASCII character ²
when it is appropriate. Vive la Unicode!

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

[Pascal J. Bourguignon]

Rusi <rustompmody@gmail.com> writes:

> On Sunday, August 2, 2015 at 7:06:24 AM UTC+5:30, Pascal J. Bourguignon wrote:
>> Emanuel Berg writes:
>> 
>> > Marcin Borkowski writes:
>> >
>> >>> Hi all, so I'm still using plists, though I'm less
>> >>> and less sure that they are actually better than
>> >>> alists for my use-case. Now I need to delete all
>> >>> properties whose value is nil. I'm using this
>> >>> function:
>> >
>> > Try this:
>> >
>> > (require 'cl)
>> >
>> > (defun plist-drop-nil-props (l)
>> >   (let((new)
>> >        (prop nil) )
>> >     (cl-loop for x in l
>> >              do (if (or (setq prop (not prop)) x)
>> >                     (setq new (append new (list x)))
>> >                   (setq new (butlast new))))
>> >     new))
>> 
>> This is horrible. Again, you can't prevent yourself writing O(n²) code
>> when O(n) would do perfectly.
>
> Hey Pascal!
> If O(n²) is 'horrible' what is O(n³)? And O(n⁴) ?
> And the stuff in NP?
> [I suppose the french lexicon has many adjectives...]

What's horrible is the ratio between the actual O(.) over the possible
O(.).


> BTW: Thanks for being civilized/cultured and using a non-ASCII character ²
> when it is appropriate. Vive la Unicode!

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> This is horrible. Again, you can't prevent yourself
>> writing O(n²) code when O(n) would do perfectly.
>
> Is it `append' or `butlast' that is linear as well?

Both.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

>>> This is horrible. Again, you can't prevent
>>> yourself writing O(n²) code when O(n) would
>>> do perfectly.
>>
>> Is it `append' or `butlast' that is linear as well?
>
> Both.

OK!

It would be useful to have a list with the time
complexities of all the list operators. Because here
(with `append' and `butlast') it isn't clear from what
those functions do that they are linear. On the
contrary: if we think of an open bike chain in
a workshop, then to put another link at either end
isn't linear, it is O(1), as is removing a link from
either end.

So I think my algorithm is actually linear (but not
the implementation you saw) if only I replaced those
functions with manually re-linking the items (because
if the list is built manually, the last item could be
stored, and then linked further to in constant time
which would imply appending to the list as that item
is already part of the list, the last part) - I don't
know how to do that right now, perhaps I'll be back if
I don't find something else to do...

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>>>> This is horrible. Again, you can't prevent
>>>> yourself writing O(n²) code when O(n) would
>>>> do perfectly.
>>>
>>> Is it `append' or `butlast' that is linear as well?
>>
>> Both.
>
> OK!
>
> It would be useful to have a list with the time
> complexities of all the list operators. Because here
> (with `append' and `butlast') it isn't clear from what
> those functions do that they are linear. On the
> contrary: if we think of an open bike chain in
> a workshop, then to put another link at either end
> isn't linear, it is O(1), as is removing a link from
> either end.

Depends on what end of the chain you hold.

To make it easier, imagine this bike chain, but 10 km long, obviously,
you have one end in hand, and the other is stored three workshop beyond.
To find this other end, you have to go thru each link.  O(n).


There is no such list of complexities because:

1- it is obvious. When you've studied lisp, you have implemented most of
   them.

2- in most cases, the algorithms are not specified, so an implementation
   would be free to provide something more efficient, if it was possible.

3- there is some expectations on the part of CL users, and sometimes an
   implementation may use a worse algorithm. Then its users will
   complain and a better algorithm is implemented.  So mostly all
   implementations have similar time and space complexities.

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.


> So I think my algorithm is actually linear (but not
> the implementation you saw) if only I replaced those
> functions with manually re-linking the items (because
> if the list is built manually, the last item could be
> stored, and then linked further to in constant time
> which would imply appending to the list as that item
> is already part of the list, the last part) - I don't
> know how to do that right now, perhaps I'll be back if
> I don't find something else to do...

Absolutely.

Also, notice that doing that, or consing onto the beginning of the list
and calling nreverse when you're done are equivalent time-complexity
wise.  There may be some difference re: cache in actual contemporaneous
computers but it can be seen only on very long lists.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
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 :)

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Also, notice that doing that, or consing onto the
> beginning of the list and calling nreverse when
> you're done are equivalent time-complexity wise.
> There may be some difference re: cache in actual
> contemporaneous computers but it can be seen only on
> very long lists.

This only uses `cons', `cdr', and `nreverse', so it is
linear, right? ("linear" only from going thru the
input list.)

(require 'cl)

(defun plist-drop-nil-props (l)
  (let ((new)
        (nil-prop)
        (prop) )
    (cl-loop for x in l
             do (if (setq prop (not prop))
                    (if x (setq new (cons x new))
                      (setq nil-prop t))
                  (if x
                      (if nil-prop (setq nil-prop nil)
                        (setq new (cons x new))   )
                    (setq new (cdr new) ))))
    (nreverse new) ))

;; (plist-drop-nil-props '(nil 1 a 1 b 2 c nil d nil e 5 g nil h) )
;; => (a 1 b 2 e 5 h)

So the list so far:

linear: butlast, append
constant: cons, cdr, nreverse

But the OP should probably use yours anyway... :)

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[John Mastro]

> This only uses `cons', `cdr', and `nreverse', so it is
> linear, right? ("linear" only from going thru the
> input list.)
>
> (require 'cl)
>
> (defun plist-drop-nil-props (l)
>   (let ((new)
>         (nil-prop)
>         (prop) )
>     (cl-loop for x in l
>              do (if (setq prop (not prop))
>                     (if x (setq new (cons x new))
>                       (setq nil-prop t))
>                   (if x
>                       (if nil-prop (setq nil-prop nil)
>                         (setq new (cons x new))   )
>                     (setq new (cdr new) ))))
>     (nreverse new) ))

I took a swing at this too for the fun of it. Here's what I ended
up with:

    (defun plist-drop-nil-props (plist)
      (let* ((result (list 'head))
             (last result))
        (cl-loop for (key val) on plist by #'cddr do
                 (when-let (new (and val (list key val)))
                   (setcdr last new)
                   (setq last (cdr new))))
        (cdr result)))

The `when-let' macro is new in Emacs 25 but obviously it can be
trivially replaced with `let' and `when' (or `-when-let' from
dash.el).

-- 
john

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

[John Mastro]

>     (defun plist-drop-nil-props (plist)
>       (let* ((result (list 'head))
>              (last result))
>         (cl-loop for (key val) on plist by #'cddr do
>                  (when-let (new (and val (list key val)))
>                    (setcdr last new)
>                    (setq last (cdr new))))
>         (cdr result)))

Or the same thing with `while' in place of `cl-loop':

    (defun drop-nil-props (plist)
      (let* ((result (list 'head))
             (last result))
        (while plist
          (let* ((key (pop plist))
                 (val (pop plist))
                 (new (and val (list key val))))
            (when new
              (setcdr last new)
              (setq last (cdr new)))))
        (cdr result)))

-- 
john

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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> 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
    object.

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

    Description:

    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.
So:

(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
   implementations.


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)
  #!+sb-doc
  "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)
                                  rest)
                     ;; 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)
                      current)
                     ((consp current)
                      (let ((result (truly-the cons (list (car current)))))
                        (append-into result
                                     (cdr current)
                                     rest)
                        result))
                     ((null current)
                      (append1 rest))
                     (t
                      (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:

LISPFUN(append,seclass_read,0,0,rest,nokey,0,NIL)
{ /* (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
          error_list(list1);
      else {
        /* (append list1 STACK_0), and list1 is a Cons: */
        /* Copy list1 and keep last Cons: */
        var object run;
        pushSTACK(list1);
        {
          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;
          pushSTACK(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))) ????
          error_proper_list_dotted(TheSubr(subr_self)->name,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) */
		FEtype_error_proper_list(head);
	}
	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) */
                        FEtype_error_proper_list(head);
                }
                *tail = ecl_va_arg(rest);
        }
	@(return head)
@)


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> 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!

In principle I don't disagree with either claim (that
reading code and re-implementing basic algorithms and
data structures is educational). But at this point
that kind of sparring doesn't fry my diodes. I only
want to solve real problems that has to do with real
systems. The small exception I make is when people ask
on this list. Sometimes that makes me do stuff
I normally wouldn't. It is a pleasant game.

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>> Also, notice that doing that, or consing onto the
>> beginning of the list and calling nreverse when
>> you're done are equivalent time-complexity wise.
>> There may be some difference re: cache in actual
>> contemporaneous computers but it can be seen only on
>> very long lists.
>
> This only uses `cons', `cdr', and `nreverse', so it is
> linear, right? ("linear" only from going thru the
> input list.)

Being O(n) doesn't come automatically by using only cons cdr and
nreverse.  It depends on the structure of the algorithm!
http://discrete.gr/complexity/

> (require 'cl)
>
> (defun plist-drop-nil-props (l)
>   (let ((new)
>         (nil-prop)
>         (prop) )
>     (cl-loop for x in l

Here you are doing the loop body once for each element in the list l.
Therefore you will be repeating the loop body (length l) times.
The complexity of your algorithm will therefore be:

    O( (* (length l) (complexity-of loop-body) )

>              do (if (setq prop (not prop))
>                     (if x
                        (setq new (cons x new))
>                       (setq nil-prop t))

NEVER put the then on the same line as the test!

>                   (if x
>                       (if nil-prop
                          (setq nil-prop nil)
>                         (setq new (cons x new))   )
>                     (setq new (cdr new) ))))

Fortunately, your loop body contains a fixed number of instruction, that
doesn't depend on the length of the list or on any other value that
depend on the length of the list.  Therefore it is O(1)
and O( (* (length l) O(1)) ) = O(length l)

>     (nreverse new) ))

(length new) is also bound by (length l), so the complexity of
(nreverse new) is O(length l).

O(length l) + O(length l) = O(length l).

> constant: cons, cdr, nreverse

No. your call to nreverse is O(length l).


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Being O(n) doesn't come automatically by using only
> cons cdr and nreverse. It depends on the structure
> of the algorithm! http://discrete.gr/complexity/

Yes, of course. But doesn't it come automatically if
the list is iterated and there is only constant
functions in the loop body? The only thing that is
linear is the iteration of the list. If on the other
hand the body contains something that is linear as
well, as was the case with `append' and `butlast',
then it'll be linear*linear - i.e. quadratic or
O(n^2).

> NEVER put the then on the same line as the test!

... why?

> Fortunately, your loop body contains a fixed number
> of instruction, that doesn't depend on the length of
> the list or on any other value that depend on the
> length of the list. Therefore it is O(1) and O( (*
> (length l) O(1)) ) = O(length l)

"Fortune" has nothing to do with it - I knew this
algorithm was linear all the time and when you
identified the linear calls in the body I replaced
those and now the implementation is linear as well.

>> constant: cons, cdr, nreverse
>
> No. your call to nreverse is O(length l).

Since it is outside of the loop body it doesn't
change the "artificial" complexity, but OK:

    constant: cdr, cons
    linear:   append, butlast, nreverse

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>> NEVER put the then on the same line as the test!
>
> ... why?

because it makes it confusing to read.  
If you do that, we have to count the parentheses!!!


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

>>> NEVER put the then on the same line as the test!
>>
>> ... why?
>
> because it makes it confusing to read.

I think it looks good. Often the condition is short
(it should be short) so there is plenty of space to
use on that line.

> If you do that, we have to count the parentheses!!!

Why, and when?

I have done that all the time and not once counted
parentheses:

    (if nil-prop (setq nil-prop nil)
      (setq new (cons x new)) )

Try this:

    ;; parentheses
    (show-paren-mode t)
    (defvar show-paren-delay)
    (setq show-paren-delay 0)

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Pascal J. Bourguignon]

Emanuel Berg <embe8573@student.uu.se> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com>
> writes:
>
>>>> NEVER put the then on the same line as the test!
>>>
>>> ... why?
>>
>> because it makes it confusing to read.
>
> I think it looks good. Often the condition is short
> (it should be short) so there is plenty of space to
> use on that line.
>
>> If you do that, we have to count the parentheses!!!
>
> Why, and when?

Compare those two forms:

         (if (and (some-predicate-p a) (= a 1) (print (list a (some-function a))))
            (print b))
         (if (and (some-predicate-p a) (= a 1)) (print (list a (some-function a)))
            (print b))


and then compare those two forms:

         (when (and (some-predicate-p a) (= a 1) (print (list a (some-function a))))
            (print b))
         (if (and (some-predicate-p a) (= a 1))
            (print (list a (some-function a)))
            (print b))



> I have done that all the time and not once counted
> parentheses:
>
>     (if nil-prop (setq nil-prop nil)
>       (setq new (cons x new)) )

This is very bad style.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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

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

[Emanuel Berg]

"Pascal J. Bourguignon" <pjb@informatimago.com>
writes:

> Compare those two forms:
>
>          (if (and (some-predicate-p a) (= a 1) (print (list a (some-function a))))
>             (print b))
>          (if (and (some-predicate-p a) (= a 1)) (print (list a (some-function a)))
>             (print b))
>
>
> and then compare those two forms:
>
>          (when (and (some-predicate-p a) (= a 1) (print (list a (some-function a))))
>             (print b))
>          (if (and (some-predicate-p a) (= a 1))
>             (print (list a (some-function a)))
>             (print b))

This problem is not a consequence of writing the
"then" branch on the same line but having the
condition complicated and too long lines in general.

If you don't do neither there is nothing wrong with
having not only the "then" branch but *both* branches
on the same line:

    (if long "&filters=long&lclk=long" "")

-- 
underground experts united
http://user.it.uu.se/~embe8573

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

[Pascal J. Bourguignon]

Marcin Borkowski <mbork@mbork.pl> writes:

> OK, so what about this?  Is there a better way (which would probably
> mean, is such function already defined)?
>
> (defun alist-clear (alist)
>   "Return ALIST with all pairs with nil value deleted."
>   (if alist

Better use when in this case.

>     (if (cdar alist)
> 	      (cons (car alist)
>     	        (alist-clear (cdr alist)))

The bad thing (shared with your plist-clear) of this, is that it's a
non-terminal recursive call, and therefore it will use O(n) stack space
with n = (length alist).  Ie. it will break for not so long alists.

See the variable max-lisp-eval-depth.

> 	      (alist-clear (cdr alist)))))


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“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