beginnerquestion (nconc)

beginnerquestion (nconc)

[Stefan Huchler]

Hello,

I am a bit anoyed by push and reverse lists its not very straightforward
solution to create lists in loops, I found in the doku the nconc macro,
which looks like some sort of push that puts sequences at the end
instead of the beginning.

So I tried to use it instead of push but it behaves strange, it only
works with nonempty lists:

Code to replace:

(setq test '())
(push '(a) test)
(push '(b) test)
(print (reverse test))

What I would expect to work:

(setq test2 '())
(nconc test2 '((a)))
(nconc test2 '((b)))
(print test2)

But only if I setq test2 the value of the first nconc expression it
works. Which is ok for that example but does not work very well in a
loop.

Is there a trick or another expression/macro that does what I want?

I guess there is add-to-list but it removes equal elements what I dont
want.

Thank you.

Re: beginnerquestion (nconc)

[Thien-Thi Nguyen]

[-- Attachment #1: Type: text/plain, Size: 1351 bytes --]


() Stefan Huchler <stefan.huchler@mail.de>
() Fri, 17 Mar 2017 06:58:17 +0100

   I found in the doku the nconc macro, which looks like some
   sort of push that puts sequences at the end instead of the
   beginning.

Was that documentation by any chance "(elisp) Rearrangement"?
That info node describes "A common pitfall...".

Personally, these days i prefer ‘cl-loop’ for non-trivial stuff:

 (cl-loop
  for n below 5
  collect (intern (string (+ ?a n))))

 => (a b c d e)

If you MUST use ‘nconc’, a common trick is to init the var w/ a
throwaway head, to be ignored (afterwards) via ‘(cdr var)’.

 (setq test3 (list 'MGMT))  ; overhead?  underfoot?  both?  :-D
 (nconc test3 (list '(a)))
 (nconc test3 (list '(b)))
 (cdr test3)

 => ((a) (b))

This example takes care to avoid quoted literals for the init
and top-level cons'ed objects.  I also dropped ‘print’ because
that happens automagically in the *scratch* buffer.

BTW, ‘nconc’ is not a macro.  I see this from ‘C-h f nconc RET’.

-- 
Thien-Thi Nguyen -----------------------------------------------
 (defun responsep (query)
   (pcase (context query)
     (`(technical ,ml) (correctp ml))
     ...))                              748E A0E8 1CB8 A748 9BFA
--------------------------------------- 6CE4 6703 2224 4C80 7502


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: beginnerquestion (nconc)

[Thien-Thi Nguyen]

[-- Attachment #1: Type: text/plain, Size: 958 bytes --]


() Thien-Thi Nguyen <ttn@gnu.org>
() Fri, 17 Mar 2017 08:33:13 +0100

   [...] non-trivial stuff:

    (cl-loop
     for n below 5
     collect (intern (string (+ ?a n))))

    => (a b c d e)

Ugh, how lame.  In the spirit of ‘nconc’... append another!

(cl-loop
 for gnu below (/ (+ 4 2)
                  (/ 4 2))
 collect (intern
          (string
           (+ 42 (* gnu (+ 4 2))
              42 (+ gnu (+ 4 2))
              42 (- (+ 4 2 (/ (* 4 2)
                              (* 4 2)))
                    (* (+ 4 2)
                       (+ 4 2)))))))

I'm not against lameness, but it seems to be "again"st me.  :-D

-- 
Thien-Thi Nguyen -----------------------------------------------
 (defun responsep (query)
   (pcase (context query)
     (`(technical ,ml) (correctp ml))
     ...))                              748E A0E8 1CB8 A748 9BFA
--------------------------------------- 6CE4 6703 2224 4C80 7502

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: beginnerquestion (nconc)

[Stefan Huchler]

Thien-Thi Nguyen <ttn@gnu.org> writes:

> Was that documentation by any chance "(elisp) Rearrangement"?
> That info node describes "A common pitfall...".

possible, but the pitfall more looks like 2 symbols are the the equal
object, I dont see how that refers to that problem.

> Personally, these days i prefer ‘cl-loop’ for non-trivial stuff:
>
>  (cl-loop
>   for n below 5
>   collect (intern (string (+ ?a n))))
>
>  => (a b c d e)

I thought the reason why rms dont likes/supports commonlisp is because
its so ugly api? If push + nconc (and no other elisp alternative does
the right thing, and you get forced to use a setq + nreverse at the end)
I have a very different idea about what ugly is apperently.

> If you MUST use ‘nconc’, a common trick is to init the var w/ a
> throwaway head, to be ignored (afterwards) via ‘(cdr var)’.
>
>  (setq test3 (list 'MGMT))  ; overhead?  underfoot?  both?  :-D
>  (nconc test3 (list '(a)))
>  (nconc test3 (list '(b)))
>  (cdr test3)

because I need that a..b in that specific varible tabulated-list-entries

that means I need to do a:

(setq tabulated-list-entries (cdr tabulated-list-entries))

which is horrible code.

I guess using a shorter 2nd symbol before the setq makes the source look
slightly less horrible.

So to make it short I have to live with this horrible state or use some
custom own wrapper, I am shure I am the first who tries such stuff in
elisp, cracy me. (sorry need my green tea to get out of troll mode :) )

I just wonder with that limitation I dont see any usecase for nconc, how
are you supposed to initialise with setq the first value in a loop, that
makes zero sense.

Well lets try it differently, maybe my way of iterating through stuff is
bad thats the code I want to be cleaner:

  (setq tabulated-list-entries '())
  (let* ((items (cdr (assoc 'items kodi-properties))))
    (dotimes (number (length items))
      (let* ((item (elt items number))
	     (title (or ;; (cdr (assoc 'title item))
		     "None"))
	     (id number))
	(push (list `(,id)
		    (vector `(,title id ,id)))
	      tabulated-list-entries)
	)))
  (setq tabulated-list-entries (nreverse tabulated-list-entries))

maybe some lambda magic? I rewrote it from a dolist version because I
need the iterator for the id.

if nreverse would directly change tabulated-list-entries I could live
with that, even that would still be ugly, but really such clunky ugly
setq statement to get what you expect in the first place?

I guess cdr with fake entry seems to be the least horrible solution of
the suggestions I guess

Anyway...

Thank You!

Re: beginnerquestion (nconc)

[Yuri Khan]

On Fri, Mar 17, 2017 at 12:58 PM, Stefan Huchler <stefan.huchler@mail.de> wrote:

> I am a bit anoyed by push and reverse lists its not very straightforward
> solution to create lists in loops, I found in the doku the nconc macro,
> which looks like some sort of push that puts sequences at the end
> instead of the beginning.

You are probably annoyed because you are familiar with list
implementations in other languages where appending an element is a
cheap operation. For example, with a doubly linked list, appending at
either end is constant time.

However, Lisp uses singly linked lists. Appending at the start is a
matter of allocating a single cons cell and setting its cdr to point
to the old head of the list. However, appending at the end requires
traversing the whole list to find its last cell, and then adding a new
cell there. That’s what nconc does. So if your list is 1000 items
long, populating it from beginning to end takes roughly 500000
operations. Populating from the end to beginning and then reversing
will only take on the order of 3000 operations.

Also, the empty list is a special case. It is represented as nil and
does not *have* a last cell that nconc could modify. That’s why nconc
does not work on the empty list.

Re: beginnerquestion (nconc)

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Fri, Mar 17, 2017 at 03:19:28PM +0100, Stefan Huchler wrote:

[...]

> I have a very different idea about what ugly is apperently.

Welcome to diversity :)

- -- tomás "but my diversity is better than yours"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEARECAAYFAljL90sACgkQBcgs9XrR2kYengCfXMWxBJ+F1pwSdmt3juYratAL
w7YAn1g+MS9QS/bUBWAcHayv6kqhuSME
=VtrX
-----END PGP SIGNATURE-----

Re: beginnerquestion (nconc)

[Stefan Huchler]

Yuri Khan <yuri.v.khan@gmail.com> writes:

> You are probably annoyed because you are familiar with list
> implementations in other languages where appending an element is a
> cheap operation. For example, with a doubly linked list, appending at
> either end is constant time.
>
> However, Lisp uses singly linked lists. Appending at the start is a
> matter of allocating a single cons cell and setting its cdr to point
> to the old head of the list. However, appending at the end requires
> traversing the whole list to find its last cell, and then adding a new
> cell there. That’s what nconc does. So if your list is 1000 items
> long, populating it from beginning to end takes roughly 500000
> operations. Populating from the end to beginning and then reversing
> will only take on the order of 3000 operations.

Hello Yuri,

thanks at least I see know WHY it is designed that way, performence.

But if I have to reverse, wouldnt it be easier that there is some sort
of:

(yreverse sequence)

that alters the sequence directly, or overwrites it.

instead of:

(setq sequence (nreverse sequence))

would make it less ugly.

RE: beginnerquestion (nconc)

[Drew Adams]

> if I have to reverse, wouldnt it be easier that there is some
> sort of: (yreverse sequence) that alters the sequence directly,
> or overwrites it. instead of: (setq sequence (nreverse sequence))

You can write macros to do this kind of thing, if you think
using the usual Lisp cliches is ugly.

(defmacro my-list-var-reverse (list-var)
  "Set variable LIST-VAR to the reverse of its value.
LIST-VAR is a symbol whose `symbol-value' is a list."
  `(setq ,list-var (nreverse ,list-var)))

(setq aaa '(1 2 3 4))
(my-list-var-reverse 'aaa)
(symbol-value 'aaa) ; ==> (4 3 2 1)

(`nreverse' acts only on lists, not on sequences in general.)

RE: beginnerquestion (nconc)

[Drew Adams]

> You can write macros to do this kind of thing, if you think
> using the usual Lisp cliches is ugly.
                         ^
                       cliche

Re: beginnerquestion (nconc)

[Stefan Monnier]

> (setq sequence (nreverse sequence))

In many cases, the (nreverse sequence) is actually returned or used in
so me function call, so there's no need to `setq' it.


        Stefan

Re: beginnerquestion (nconc)

[Michael Heerdegen]

Stefan Huchler <stefan.huchler@mail.de> writes:

> (setq sequence (nreverse sequence))

FWIW that's equivalent to

  (cl-callf nreverse sequence)

if you want to avoid to write out the symbol name twice.


Michael.

Re: beginnerquestion (nconc)

[Stefan Huchler]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> (setq sequence (nreverse sequence))
>
> In many cases, the (nreverse sequence) is actually returned or used in
> so me function call, so there's no need to `setq' it.
>
>
>         Stefan


I need the value for a tabulated list, so I dont see a way to not use
setq here?


(setq tabulated-list-entries (nreverse tabulated-list-entries))

greetings

Stefan

Re: beginnerquestion (nconc)

[Stefan Huchler]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> (setq sequence (nreverse sequence))
>
> In many cases, the (nreverse sequence) is actually returned or used in
> so me function call, so there's no need to `setq' it.
>
>
>         Stefan

Well to give you more context, most of the time I used doitems +
push. and push works the "right" way. so no reversing is needed:

  (dolist (item (append (let-alist kodi-properties .items) nil))
    (push (list (spiderbit-get-id item)
		(vector `(,(spiderbit-get-name item)
			  id ,(spiderbit-get-show-id item))))
	  tabulated-list-entries))

I could revert here kodi-properties I guess to get in the end what I
want?



But now I needed a iterator in the alist assigend to the elements:

  (let* ((items (cdr (assoc 'items kodi-properties))))
    (dotimes (number (length items))
      (let* ((item (elt items number))
	     (title (or (spiderbit-get-name item)
		     "None"))
	     (id number))
	(push (list `(,id)
		    (vector `(,title id ,id)))
	      tabulated-list-entries))))
  (setq tabulated-list-entries (nreverse tabulated-list-entries))


So I would need to reverse here items and number or use something like
length - number as index?

it just dont feels very natural. I dont know.

Stefan

Re: beginnerquestion (nconc)

[John Mastro]

Stefan Huchler <stefan.huchler@mail.de> wrote:
> Well to give you more context, most of the time I used doitems +
> push. and push works the "right" way. so no reversing is needed:
>
>   (dolist (item (append (let-alist kodi-properties .items) nil))
>     (push (list (spiderbit-get-id item)
>                 (vector `(,(spiderbit-get-name item)
>                           id ,(spiderbit-get-show-id item))))
>           tabulated-list-entries))
>
> I could revert here kodi-properties I guess to get in the end what I
> want?
>
>
>
> But now I needed a iterator in the alist assigend to the elements:
>
>   (let* ((items (cdr (assoc 'items kodi-properties))))
>     (dotimes (number (length items))
>       (let* ((item (elt items number))
>              (title (or (spiderbit-get-name item)
>                      "None"))
>              (id number))
>         (push (list `(,id)
>                     (vector `(,title id ,id)))
>               tabulated-list-entries))))
>   (setq tabulated-list-entries (nreverse tabulated-list-entries))
>
>
> So I would need to reverse here items and number or use something like
> length - number as index?
>
> it just dont feels very natural. I dont know.

It's not always a good candidate, but often you can use `mapcar' instead
of `push' and `nreverse'.

As an example (with the warning that I'm not familiar with kodi,
spiderbit, etc., so there may be problems with this):

(setq tabulated-list-entries
      (let ((id 0))
        (mapcar (lambda (item)
                  (let* ((title (or (spiderbit-get-name item) "None"))
                         (entry (list `(,id) (vector `(,title id ,id)))))
                    (setq id (1+ id)) ;; Or (cl-incf id)
                    entry))
                (cdr (assoc 'items kodi-properties)))))

The `push' plus `nreverse' idiom felt fairly unnatural to me too when I
first encountered Lisp. Before that, my main programming experience was
in Python, where the most natural way to work with lists (which are
dynamic arrays in Python's case) is to append at the end. Now, a few
years later, it feel natural enough, but perhaps that's Stockholm
syndrome talking :)

        John

Re: beginnerquestion (nconc)

[Stefan Huchler]

John Mastro <john.b.mastro@gmail.com> writes:

> It's not always a good candidate, but often you can use `mapcar' instead
> of `push' and `nreverse'.

yes I also thought about mapcar functions and lambda in the last few hours:

  (let* ((items (cdr (assoc 'items kodi-properties)))
  	 (ids (number-sequence 0 (- (length items) 1))))
    (setq tabulated-list-entries
  	  (mapcar*
  	   (lambda (id item)
  	     (let* ((title (or ;;(cdr (assoc 'title item))
  			    (spiderbit-get-name item)
  			    "None")))
  	       (list `,id
  		     (vector `(,title id ,id)))))	 
  	   ids items) ))


I would even think about seq-position to get the id but that seems to be
not in 24.x version of seq.el

your solution looks interesting, too. first you also use at least 1
cl-... function I dont know what I have to thinb about that. isnt clisp
supposed to be ugly or bad? still everwhere you get suggestions about
it.

often the non (cl-) prefixed stuff seem to be wrappers or renamed
commonlisp functions, too?

> As an example (with the warning that I'm not familiar with kodi,
> spiderbit, etc., so there may be problems with this):
>
> (setq tabulated-list-entries
>       (let ((id 0))
>         (mapcar (lambda (item)
>                   (let* ((title (or (spiderbit-get-name item) "None"))
>                          (entry (list `(,id) (vector `(,title id ,id)))))
>                     (setq id (1+ id)) ;; Or (cl-incf id)
>                     entry))
>                 (cdr (assoc 'items kodi-properties)))))

that you can access with lambda on stuff outside the lambda I did not
know and of course makes things much easier / clean.

(ohh well I just see that you did comment out the cl-incf call).

also you used one time let and one time let* only a mistake or has that
any meaning?

I thought let* is for most cases better?

Wow and you use let after setq I never thought about that, but of course
it should/will work.

I am much about learning by doing, and to learn on concrete use cases /
needs. seems to kind of work. Meanwhile people (most important me) can
use the badly programmed but good usable kodi-remote if they want :)

> The `push' plus `nreverse' idiom felt fairly unnatural to me too when I
> first encountered Lisp. Before that, my main programming experience was
> in Python, where the most natural way to work with lists (which are
> dynamic arrays in Python's case) is to append at the end. Now, a few
> years later, it feel natural enough, but perhaps that's Stockholm
> syndrome talking :)

yes I also used much python in the past. Well its more a emacs-lisp
specific thing right? I mean common-lisp has append. its not good for
performance critical stuff and huge amounts of data... which would be
pretty irrelevant for my usecase.

But ok, if it leads me to better coding style, so be it.

I did not use map and lambda very much in the past. But should start
doing that more :)

Re: beginnerquestion (nconc)

[Michael Heerdegen]

Stefan Huchler <stefan.huchler@mail.de> writes:

> isnt clisp supposed to be ugly or bad? still everwhere you get
> suggestions about it.

It is not recommended to load "cl" because its functions don't have a
prefix, and we want to have every "optional" library use a unique
prefix.

OTOH it is absolutely ok to load cl-lib and use its stuff.


Michael.

Re: beginnerquestion (nconc)

[John Mastro]

Stefan Huchler <stefan.huchler@mail.de> wrote:
> I would even think about seq-position to get the id but that seems to be
> not in 24.x version of seq.el

From an efficiency standpoint, that also means scanning the list over
and over. It would only "really" matter if the list got largish, but
it's easy enough to avoid. Another option would be to use something like
`-map-indexed' from the `dash' library. (Incidentally, the efficiency
concern also applies to using `dotimes' plus `elt' to iterate over a
linked list).

> your solution looks interesting, too. first you also use at least 1
> cl-... function I dont know what I have to thinb about that. isnt clisp
> supposed to be ugly or bad? still everwhere you get suggestions about
> it.

People have a few different concerns with `cl' and `cl-lib':
  1. `cl' introduces lots of non-namespaced names
  2. Some people find the "cl"-prefixed names in `cl-lib' to be
     aesthetically unappealing
  3. Some people find the programming style associated with Common
     Lisp to be aesthetically unappealing

I avoid `cl' for the first reason above but the second and third don't
trouble me much.

> often the non (cl-) prefixed stuff seem to be wrappers or renamed
> commonlisp functions, too?

Yes, the idea of both `cl' and `cl-lib' is to provide Common Lisp-like
functions that aren't present in Emacs Lisp's standard library.

> also you used one time let and one time let* only a mistake or has that
> any meaning?
>
> I thought let* is for most cases better?

There is a reasonable argument to always use `let*', but my personal
habit is to use `let' by default and only use `let*' when the difference
between them is significant.

> Wow and you use let after setq I never thought about that, but of course
> it should/will work.

Yes, either way works.

> I am much about learning by doing, and to learn on concrete use cases /
> needs. seems to kind of work. Meanwhile people (most important me) can
> use the badly programmed but good usable kodi-remote if they want :)

That's a good way to learn - it's hard to beat practice and experience.

> yes I also used much python in the past. Well its more a emacs-lisp
> specific thing right? I mean common-lisp has append. its not good for
> performance critical stuff and huge amounts of data... which would be
> pretty irrelevant for my usecase.

The `push' / `nreverse' idiom is found in both Common Lisp and Scheme,
and probably other Lisps too, though I don't have experience with most
of the others.

Common Lisp, Scheme, and Emacs Lisp all have `append', but it's not the
same as Python's `list.append', because the underlying data structure is
different.

Lists in CL/Scheme/Elisp are singly-linked lists built from cons cells,
which means it's inherently inefficient to append to the end. That's the
ultimate reason for the `push' / `nreverse' style: you append at the
front (where it's efficient to do so, but results in the elements being
in reverse order), then reverse the list to get it back in the desired
order.

> But ok, if it leads me to better coding style, so be it.
>
> I did not use map and lambda very much in the past. But should start
> doing that more :)

Like any style or approach, it has its limits, but I think it's quite
nice for many common uses.

        John