Testing whether a list contains at least one non-nil element

Testing whether a list contains at least one non-nil element

[Heime]

I would like to test whether a list contains at least one non-nil element?  If I do that, then
I would be able to continue a loop where a non-nil element would mean that a match was found.

Re: Testing whether a list contains at least one non-nil element

[Jean Louis]

* Heime <heimeborgia@protonmail.com> [2022-10-25 13:18]:
> I would like to test whether a list contains at least one non-nil element?  If I do that, then
> I would be able to continue a loop where a non-nil element would mean that a match was found.

(cond ((memq nil '(1 2 nil)) (message "True, there is nil inside"))
      ((memq nil '(1 2 3)) (message "No, there is no nil inside"))) ⇒ "True, there is nil inside"


-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

Re: Testing whether a list contains at least one non-nil element

[Jean Louis]

* Heime <heimeborgia@protonmail.com> [2022-10-25 13:18]:
> 
> I would like to test whether a list contains at least one non-nil element?  If I do that, then
> I would be able to continue a loop where a non-nil element would mean that a match was found.

Previous e-mail is wrong, you asked for non-nil element and I sent for
nil. 👀

-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

Re: Testing whether a list contains at least one non-nil element

[Jean Louis]

* Heime <heimeborgia@protonmail.com> [2022-10-25 13:18]:
> 
> I would like to test whether a list contains at least one non-nil element?  If I do that, then
> I would be able to continue a loop where a non-nil element would mean that a match was found.

Here is the test for non nil element:

(elt (delq nil (list nil nil)) 0) ⇒ nil

(elt (delq nil (list nil 1)) 0) ⇒ 1

-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

Re: Testing whether a list contains at least one non-nil element

[Michael Heerdegen]

Heime <heimeborgia@protonmail.com> writes:

> I would like to test whether a list contains at least one non-nil
> element?

I'd use `cl-some': (cl-some #'identity my-list).  There are lots of
other possible solutions, like using a simple `while' loop or a `dolist'
with `catch' and `throw'.

Michael.

Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Jean Louis wrote:

>> I would like to test whether a list contains at least one
>> non-nil element? If I do that, then I would be able to
>> continue a loop where a non-nil element would mean that
>> a match was found.
>
> Here is the test for non nil element:
>
> (elt (delq nil (list nil nil)) 0) ⇒ nil
>
> (elt (delq nil (list nil 1)) 0) ⇒ 1

Interesting question ...

(cl-position-if (lambda (e) e) '(nil nil)) ; nil
(cl-position-if (lambda (e) e) '(nil 1))   ; 1

-- 
underground experts united
https://dataswamp.org/~incal

Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Michael Heerdegen wrote:

>> I would like to test whether a list contains at least one
>> non-nil element?
>
> I'd use `cl-some': (cl-some #'identity my-list).

Cute, and `identity' also works with `cl-position-if' ...

(cl-some #'identity '(nil nil)) ; nil
(cl-some #'identity '(nil 1))   ; 1

(cl-position-if #'identity '(nil nil)) ; nil
(cl-position-if #'identity '(nil 1))   ; 1

-- 
underground experts united
https://dataswamp.org/~incal

RE: [External] : Re: Testing whether a list contains at least one non-nil element

[Drew Adams]

> > I would like to test whether a list contains 
> > at least one non-nil element?
> 
> I'd use `cl-some': (cl-some #'identity my-list).
> There are lots of other possible solutions, like
> using a simple `while' loop or a `dolist' with
> `catch' and `throw'.

IOW:

(setq toto '(nil nil 3 nil nil))

(defun foo (xs)
  (while (and (not (car xs)) xs)
    (setq xs (cdr xs)))
  (car xs))

(defun bar (xs)
  (catch 'bar
    (dolist (x xs) (when x (throw 'bar t)))
    nil))

(foo toto)
(bar toto)

Or just:

(cl-member-if-not #'null toto)

Re: Testing whether a list contains at least one non-nil element

[Joost Kremers]

On Tue, Oct 25 2022, Heime wrote:
> I would like to test whether a list contains at least one non-nil element?  If I do that, then
> I would be able to continue a loop where a non-nil element would mean that a match was found.

(seq-some (lambda (e) (not (null e))) mylist)

or shorter:

(not (seq-every-p #'null mylist))

If you use dash.el, there's also --any? (or --any-p if you prefer):

(--any? (not (null it)) mylist)

HTH

-- 
Joost Kremers
Life has its moments

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Drew Adams wrote:

> (cl-member-if-not #'null toto)

Close

  (cl-member-if-not #'null '(nil nil)) ; nil
  (cl-member-if-not #'null '(nil 2))   ; (2)

But

  (cl-position-if-not #'null '(nil nil)) ; nil
  (cl-position-if-not #'null '(nil 2))   ; 1

-- 
underground experts united
https://dataswamp.org/~incal

Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Joost Kremers wrote:

>> I would like to test whether a list contains at least one
>> non-nil element? If I do that, then I would be able to
>> continue a loop where a non-nil element would mean that
>> a match was found.
>
> (seq-some (lambda (e) (not (null e))) mylist)
>
> or shorter:
>
> (not (seq-every-p #'null mylist))

Nope, at least the way I understood the question where the
loop would continue at that position, but actually anyway
those are not as good as

(cl-position-if-not #'null '(nil nil)) ; nil
(cl-position-if-not #'null '(nil   2)) ;   1

-- 
underground experts united
https://dataswamp.org/~incal

Re: Testing whether a list contains at least one non-nil element

[Heime]

Sent with Proton Mail secure email.

------- Original Message -------
On Tuesday, October 25th, 2022 at 5:25 PM, Joost Kremers <joostkremers@fastmail.fm> wrote:


> On Tue, Oct 25 2022, Heime wrote:
> 
> > I would like to test whether a list contains at least one non-nil element? If I do that, then
> > I would be able to continue a loop where a non-nil element would mean that a match was found.
> 
> 
> (seq-some (lambda (e) (not (null e))) mylist)
> 
> or shorter:
> 
> (not (seq-every-p #'null mylist))

How does your implementation (not (seq-every-p #'null mylist)) compared to 

(elt (delq nil mylist) 0) 

Re: Testing whether a list contains at least one non-nil element

[Joost Kremers]

On Tue, Oct 25 2022, Heime wrote:
> On Tuesday, October 25th, 2022 at 5:25 PM, Joost Kremers
> <joostkremers@fastmail.fm> wrote:
>> (not (seq-every-p #'null mylist))
>
> How does your implementation (not (seq-every-p #'null mylist)) compared to 
>
> (elt (delq nil mylist) 0) 

Not well, it seems:

```
(setq mylist '(nil nil nil nil nil nil nil nil nil t))

(benchmark 100000 '(elt (delq nil mylist) 0))
"Elapsed time: 0.040299s"


(benchmark 100000 '(not (seq-every-p #'null mylist)))
"Elapsed time: 0.470680s (0.187590s in 1 GCs)"



(setq mylist '(nil t nil nil nil nil nil nil nil nil t))

(benchmark 100000 '(elt (delq nil mylist) 0))
"Elapsed time: 0.035235s"


(benchmark 100000 '(not (seq-every-p #'null mylist)))
"Elapsed time: 0.361699s (0.186059s in 1 GCs)"
```

`elt` and `delq` are both implemented in C, while `seq-every-p` is a generic
function, so I guess those results aren't surprising.


-- 
Joost Kremers
Life has its moments

RE: [External] : Re: Testing whether a list contains at least one non-nil element

[Drew Adams]

> > > I would like to test whether a list contains at least one
> > > non-nil element? If I do that, then I would be able to
> > > continue a loop where a non-nil element would mean
> > > that a match was found.
> >
> > (seq-some (lambda (e) (not (null e))) mylist)
> >
> > or shorter:
> >
> > (not (seq-every-p #'null mylist))
> 
> How does your implementation (not (seq-every-p #'null mylist)) compared to
> 
> (elt (delq nil mylist) 0)

`delq' is a "destructive" operation.  It can, and
generally does, modify list structure.  Is that what
you intend?  That's something other than just doing
a "test whether a list contains at least one non-nil
element."

Be very careful and know what you're doing, and why,
if you start writing code that modifies list structure.

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Joost Kremers]

On Tue, Oct 25 2022, Drew Adams wrote:
>> > > I would like to test whether a list contains at least one
>> > > non-nil element? If I do that, then I would be able to
>> > > continue a loop where a non-nil element would mean
>> > > that a match was found.
>> >
>> > (seq-some (lambda (e) (not (null e))) mylist)
>> >
>> > or shorter:
>> >
>> > (not (seq-every-p #'null mylist))
>> 
>> How does your implementation (not (seq-every-p #'null mylist)) compared to
>> 
>> (elt (delq nil mylist) 0)
>
> `delq' is a "destructive" operation.

Oops, I didn't realise that when I wrote my reply... Should've checked...

So hopefully this gives a better idea:

```
(benchmark 100000 '(let ((mylist (list nil nil nil nil nil nil nil nil nil t)))
                     (elt (delq nil mylist) 0)))
"Elapsed time: 0.493742s (0.379511s in 2 GCs)"

(benchmark 100000 '(let ((mylist (list nil nil nil nil nil nil nil nil nil t)))
                     (not (seq-every-p #'null mylist))))
"Elapsed time: 0.923503s (0.566131s in 3 GCs)"


(benchmark 100000 '(let ((mylist (list nil t nil nil nil nil nil nil nil nil t)))
                     (elt (delq nil mylist) 0)))
"Elapsed time: 0.496120s (0.377506s in 2 GCs)"


(benchmark 100000 '(let ((mylist (list nil t nil nil nil nil nil nil nil nil t)))
                     (not (seq-every-p #'null mylist))))
"Elapsed time: 0.823751s (0.566227s in 3 GCs)"
```


-- 
Joost Kremers
Life has its moments

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Stefan Monnier via Users list for the GNU Emacs text editor]

> (benchmark 100000 '(let ((mylist (list nil nil nil nil nil nil nil nil nil t)))
>                      (elt (delq nil mylist) 0)))

The `elt` call is unnecessary.
And to avoid the destructiveness of `delq` you can use `remq`.


        Stefan

RE: [External] : Re: Testing whether a list contains at least one non-nil element

[Drew Adams]

> > (cl-member-if-not #'null toto)
> 
> Close
>   (cl-member-if-not #'null '(nil nil)) ; nil
>   (cl-member-if-not #'null '(nil 2))   ; (2)
> 
> But
>   (cl-position-if-not #'null '(nil nil)) ; nil
>   (cl-position-if-not #'null '(nil 2))   ; 1

The request was for a test of whether the input
list contains any non-nil elements.  Yes, both
`cl-member-if-not' and `cl-position-if-not' can
do that.  Or `cl-member-if' and `cl-position-if',
passing #'identity.

There are lots of ways to do it.

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Drew Adams wrote:

>>> (cl-member-if-not #'null toto)
>> 
>> Close
>>   (cl-member-if-not #'null '(nil nil)) ; nil
>>   (cl-member-if-not #'null '(nil 2))   ; (2)
>> 
>> But
>>   (cl-position-if-not #'null '(nil nil)) ; nil
>>   (cl-position-if-not #'null '(nil 2))   ; 1
>
> The request was for a test of whether the input
> list contains any non-nil elements.

Right, I thought the question was identify the spot and loop
the rest of the list from there, and the OP said something to
that extend, but actually it's unclear what solution is best
even then since one can iterate the rest of the list with
`member' as well, and maybe that's even more idiomatic than to
rely on an index to identify the starting point come think
of it.

Okay I was wrong ...

https://www.youtube.com/watch?v=6WOYnv59Bi8

> Yes, both `cl-member-if-not' and `cl-position-if-not' can do
> that. Or `cl-member-if' and `cl-position-if', passing
> #'identity.
>
> There are lots of ways to do it.

That's a good thing, but which way is the best way?

-- 
underground experts united
https://dataswamp.org/~incal

Re: Testing whether a list contains at least one non-nil element

[Jean Louis]

* Emanuel Berg <incal@dataswamp.org> [2022-10-26 15:55]:
> Jean Louis wrote:
> 
> >> I would like to test whether a list contains at least one
> >> non-nil element? If I do that, then I would be able to
> >> continue a loop where a non-nil element would mean that
> >> a match was found.
> >
> > Here is the test for non nil element:
> >
> > (elt (delq nil (list nil nil)) 0) ⇒ nil
> >
> > (elt (delq nil (list nil 1)) 0) ⇒ 1
> 
> Interesting question ...
> 
> (cl-position-if (lambda (e) e) '(nil nil)) ; nil
> (cl-position-if (lambda (e) e) '(nil 1))   ; 1

While `remq' is more suitable as not destructive one:

(elt (remq nil (list nil nil)) 0) ⇒ nil
(elt (remq nil (list nil "any")) 0) ⇒ "any"

cl- is Common Lisp prefix to conform those people who are used to
Common Lisp.  Those functions are bloated.

(defun list-has-non-nil-p (list)
  "Test if list has non nil element."
  (elt (remq nil list) 0))

(list-has-non-nil-p '(1 2 3)) ⇒ 1

(list-has-non-nil-p '(nil nil nil)) ⇒ nil



-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

RE: [External] : Re: Testing whether a list contains at least one non-nil element

[Drew Adams]

> (defun list-has-non-nil-p (list)
>   "Test if list has non nil element."
>   (elt (remq nil list) 0))

`remq' can end up needlessly traversing and
copying quite a lot of the argument LIST.

(defun remq (elt list)
  (while (and (eq elt (car list))
    (setq list (cdr list))))

  ;; Hey, we're done already.  Empty list
  ;; means no non-nil elements.  Nonempty
  ;; means the car is non-nil.
  ;;
  ;; Why do the rest of this?
  ;; Search for a nil, after the non-nil car?
  ;; Then copy the entire list.  Then delete
  ;; all nils from it?  Why on earth do this?
  (if (memq elt list)
       ^^^^
      (delq elt (copy-sequence list))
                 ^^^^^^^^^^^^^
       ^^^^^^^^^
    list))

First that removes all nils from the beginning
of LIST.  OK.  At that point either the list
is empty, and the answer is nil, or the first
list element is non-nil.  Just stop there.

Why go on, with the remainder of the list,
whose car is non-nil, searching for the next
nil?

Why then copy that entire remaining list and
then traverse it to delete all nils from it?

None of that makes sense.  Talk about "bloat"?
You're using the wrong function to do the job.

If you have a tiny list, or one where you
don't expect any non-nil elements before a
long way into the list, then maybe such wasted
effort isn't a concern.  Otherwise, it might
be.  And it's not needed.

Functions others (including I) sent for this
question don't have any of those problems.
They just traverse the list till they find a
non-nil value.  At worst, they traverse the
whole list once.

You certainly don't need to remove all nils
from the list.  If your list is 100,000,000
elements long and the first element is t, why
would you want to copy the entire list and
then remove all the nils from it?  Testing
the first element tells you the answer.

Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Jean Louis wrote:

> cl- is Common Lisp prefix to conform those people who are
> used to Common Lisp. Those functions are bloated.

The are useful (and neat), that's why people use them, not
that they are used to them from CL.

But that's a possibility and correct for some people, and why
not? They were useful there, implemented here for that reason,
and after that they have been useful here as well. This is
completely natural, it's a good thing and it happens all
the time, God willing that will continue.

So if some dude comes up with something in some other Lisp
dialect first thing we should do after finishing the morning
milk and flakes is see if we could do that same thing here as
well so we also benefit from his ingenuity and overall just
elevate our game any and all ways possible ...

> (defun list-has-non-nil-p (list)
>   "Test if list has non nil element."
>   (elt (remq nil list) 0))

-1

-- 
underground experts united
https://dataswamp.org/~incal

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Jean Louis]

* Drew Adams <drew.adams@oracle.com> [2022-10-27 06:54]:

>   ;; Why do the rest of this?
>   ;; Search for a nil, after the non-nil car?
>   ;; Then copy the entire list.  Then delete
>   ;; all nils from it?  Why on earth do this?
>   (if (memq elt list)
>        ^^^^
>       (delq elt (copy-sequence list))
>                  ^^^^^^^^^^^^^
>        ^^^^^^^^^
>     list))

I get your reasoning. Maybe my function was not named correctly and
then your logic jumps in. 

> You certainly don't need to remove all nils
> from the list.  If your list is 100,000,000
> elements long and the first element is t, why
> would you want to copy the entire list and
> then remove all the nils from it?  Testing
> the first element tells you the answer.

I get the reasoning, you are right, though maybe not in the context of
testing if list has at least one non nil element. I am not sure, you
know is not easy to grasp all.

What I know is that by testing the first element does not tell the
answer if list has any non nil element:

(let ((my-list '(nil nil nil nil)))
    (car my-list)) ⇒ nil

(let ((my-list '(nil nil nil nil 1)))
    (car my-list)) ⇒ nil

So testing the first element did not give me the answer that
 my-list has one non-nil element.

Maybe you can show in Emacs Lisp practically how do you mean it.

-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Jean Louis wrote:

>> You certainly don't need to remove all nils from the list.
>> If your list is 100,000,000 elements long and the first
>> element is t, why would you want to copy the entire list
>> and then remove all the nils from it? Testing the first
>> element tells you the answer.
>
> [...] What I know is that by testing the first element does
> not tell the answer if list has any non nil element:
>
> (let ((my-list '(nil nil nil nil)))
>     (car my-list)) ⇒ nil
>
> (let ((my-list '(nil nil nil nil 1)))
>     (car my-list)) ⇒ nil
>
> So testing the first element did not give me the answer that
>  my-list has one non-nil element.

He means that case shows how poor that solution would be,
which means it's just not a good solution.

There are several ways to search a list for a specific element
but they rely on sorting the list first and if that isn't
desired is there really any other way than to examine the
items one by one?

In that case it's the Linear Search algorithm which is at
worst O(n), i.e. the whole list has to be searched until the
element is found at the last element or not found at all.

OTOH if sorting is done then one does Quick Sort first, which
is at worst O(n^2), then Binary Search on the result which is
at worst O(log n), so combined they are, at worst, worse than
O(n^2) or in other words, much worse than Linear Search at
O(n).

However if the data is *kept* sorted after the sorting and
insertions are made in a way that will uphold the order, that
means Binary Search can be used directly, that means we are at
a much better O(log n) again compared to Linear Search at
O(n) ...

-- 
underground experts united
https://dataswamp.org/~incal

RE: [External] : Re: Testing whether a list contains at least one non-nil element

[Drew Adams]

> >   ;; Why do the rest of this?
> >   ;; Search for a nil, after the non-nil car?
> >   ;; Then copy the entire list.  Then delete
> >   ;; all nils from it?  Why on earth do this?
> >   (if (memq elt list)
> >        ^^^^
> >       (delq elt (copy-sequence list))
> >                  ^^^^^^^^^^^^^
> >        ^^^^^^^^^
> >     list))
> 
> I get your reasoning. Maybe my function was not
> named correctly and then your logic jumps in.
> 
> > You certainly don't need to remove all nils
> > from the list.  If your list is 100,000,000
> > elements long and the first element is t, why
                     ^
                     IF
> > would you want to copy the entire list and
> > then remove all the nils from it?  Testing
> > the first element tells you the answer.
> 
> I get the reasoning, you are right, though maybe not in the context of
> testing if list has at least one non nil element. I am not sure, you
> know is not easy to grasp all.
> 
> What I know is that by testing the first element does not tell the
> answer if list has any non nil element:...
> So testing the first element did not give me the answer that
> my-list has one non-nil element.

No one said it did.  Please reread what I wrote.

In the worst case for your code, the first
element IS non-nil and you spend forever doing
useless stuff.  In no case is your code as
efficient as just testing each list element,
starting at the beginning, and STOPPING as
soon as you find a non-nil element.

> Maybe you can show in Emacs Lisp practically how do you mean it.

I think I did.  Please reread.  Try your code.
Try it in the debugger.  Try the code that
others have sent.  Look at that code: it just
tests till it finds a non-nil element, then
stops - that's the point.  And no list copying.

It's not important perhaps, if your use case
doesn't care about such things.  But it's not
a bad idea to look at the code that defines
functions you use - in this case `remq', to
see how it behaves.  That's the real point
here.

And yes, the `cl-*' functions can be, and
typically are, implemented in a performant
way.

If you find an Emacs implementation of a CL
function that's not as good as it could be,
please report that.

Emacs's `cl-*' emulation is not a real,
performant CL implementation, nor does it
pretend to be.  But in some cases it could
perhaps be improved.

Elisp and CL (was: Re: [External] : Re: Testing whether a list contains at least one non-nil element)

[Emanuel Berg]

Drew Adams wrote:

> And yes, the `cl-*' functions can be, and typically are,
> implemented in a performant way. [...]
>
> Emacs's `cl-*' emulation is not a real, performant CL
> implementation [...] But in some cases it could perhaps
> be improved.

Most definitely, and everything can always be improved.

We should stop thinking of Elisp as the configuration and
extension language of Emacs.

If we care about Lisp, which has been on the back foot for
decades to the point it's now defeated in all of Gaul. All of
it? No - there is still a small pocket of resistence. And it's
called Emacs!

We'll never, ever get a better storefront for Lisp than Emacs.

Elisp should be considered Lisp's last hope and we should do
everything we can to improve and modernize it every way we
can ...

So speaking of CL, why is that better? Because it is much
faster than Elisp, right?

But why can't Elisp be fast as well?

  If anything can start anew
  then everything must continue

-- 
underground experts united
https://dataswamp.org/~incal

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Jean Louis]

* Drew Adams <drew.adams@oracle.com> [2022-10-27 18:54]:
> In the worst case for your code, the first element IS non-nil and
> you spend forever doing useless stuff.  In no case is your code as
> efficient as just testing each list element, starting at the
> beginning, and STOPPING as soon as you find a non-nil element.

Of course I agree with the thought in general.

Is it this below?

(defun check-if-any-elt-is-non-nil (list)
  (let (there-is)
    (while (and list (not there-is))
      (when (car list) (setq there-is t))
      (setq list (cdr list)))
    there-is))

(check-if-any-elt-is-non-nil '(nil nil nil nil nil nil nil nil 1 nil)) ⇒ t

(check-if-any-elt-is-non-nil '(nil nil nil nil nil nil nil nil nil)) ⇒ nil

(benchmark 10000000 (check-if-any-elt-is-non-nil (append (list 1) (make-list 1000000 nil)))) ⇒ "Elapsed time: 0.771948s"

(benchmark 10000000 (check-if-any-elt-is-non-nil (append (make-list 1000000 nil) (list 1) ))) ⇒ "Elapsed time: 0.744323s"

-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Jean Louis wrote:

> (defun check-if-any-elt-is-non-nil (list)
>   (let (there-is)
>     (while (and list (not there-is))
>       (when (car list) (setq there-is t))
>       (setq list (cdr list)))
>     there-is))

(require 'cl-lib)

(defun has-non-nil (lst)
  (cl-loop for e in lst
           until e
           finally return e) )

(benchmark 10000000 (has-non-nil (append (list 1) (make-list 1000000 nil)))) ; "Elapsed time: 0.330502s"
(benchmark 10000000 (has-non-nil (append          (make-list 1000000 nil)))) ; "Elapsed time: 0.570150s"

-- 
underground experts united
https://dataswamp.org/~incal

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[tomas]

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

On Thu, Oct 27, 2022 at 11:38:57PM +0300, Jean Louis wrote:
> * Drew Adams <drew.adams@oracle.com> [2022-10-27 18:54]:
> > In the worst case for your code, the first element IS non-nil and
> > you spend forever doing useless stuff.  In no case is your code as
> > efficient as just testing each list element, starting at the
> > beginning, and STOPPING as soon as you find a non-nil element.
> 
> Of course I agree with the thought in general.
> 
> Is it this below?
> 
> (defun check-if-any-elt-is-non-nil (list)
>   (let (there-is)
>     (while (and list (not there-is))
>       (when (car list) (setq there-is t))
>       (setq list (cdr list)))
>     there-is))

If you are doing it "by hand", why not indulge in Lisp's
"classic elegance", like so:

  (defun has-non-nil (lst)
    (cond
     ((null lst) nil)
     ((consp lst) (or (not (null (car lst))) (has-non-nil (cdr lst))))
     (t (error "Not a proper list! You cheater!"))))

Cheers
-- 
t

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

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Jean Louis]

* tomas@tuxteam.de <tomas@tuxteam.de> [2022-10-28 07:50]:
> On Thu, Oct 27, 2022 at 11:38:57PM +0300, Jean Louis wrote:
> > * Drew Adams <drew.adams@oracle.com> [2022-10-27 18:54]:
> > > In the worst case for your code, the first element IS non-nil and
> > > you spend forever doing useless stuff.  In no case is your code as
> > > efficient as just testing each list element, starting at the
> > > beginning, and STOPPING as soon as you find a non-nil element.
> > 
> > Of course I agree with the thought in general.
> > 
> > Is it this below?
> > 
> > (defun check-if-any-elt-is-non-nil (list)
> >   (let (there-is)
> >     (while (and list (not there-is))
> >       (when (car list) (setq there-is t))
> >       (setq list (cdr list)))
> >     there-is))
> 
> If you are doing it "by hand", why not indulge in Lisp's
> "classic elegance", like so:
> 
>   (defun has-non-nil (lst)
>     (cond
>      ((null lst) nil)
>      ((consp lst) (or (not (null (car lst))) (has-non-nil (cdr lst))))
>      (t (error "Not a proper list! You cheater!"))))

✔️ Beautiful 

-- 
Jean

Take action in Free Software Foundation campaigns:
https://www.fsf.org/campaigns

In support of Richard M. Stallman
https://stallmansupport.org/

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Michael Heerdegen]

<tomas@tuxteam.de> writes:

> If you are doing it "by hand", why not indulge in Lisp's
> "classic elegance", like so:
>
>   (defun has-non-nil (lst)
>     (cond
>      ((null lst) nil)
>      ((consp lst) (or (not (null (car lst))) (has-non-nil (cdr lst))))
>      (t (error "Not a proper list! You cheater!"))))

You don't want to implement such functions in Emacs with recursion
because you'll easily hit `max-lisp-eval-depth' when they are called.
Sorry to tell you, but a loop is the preferable way in Elisp.

Michael.

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Stefan Monnier via Users list for the GNU Emacs text editor]

Michael Heerdegen [2022-10-28 08:20:45] wrote:
> <tomas@tuxteam.de> writes:
>> If you are doing it "by hand", why not indulge in Lisp's
>> "classic elegance", like so:
>>
>>   (defun has-non-nil (lst)
>>     (cond
>>      ((null lst) nil)
>>      ((consp lst) (or (not (null (car lst))) (has-non-nil (cdr lst))))
>>      (t (error "Not a proper list! You cheater!"))))
>
> You don't want to implement such functions in Emacs with recursion
> because you'll easily hit `max-lisp-eval-depth' when they are called.

Indeed (and it's significantly slower than the corresponding loop
without function calls).

> Sorry to tell you, but a loop is the preferable way in Elisp.

Luckily, since Emacs-28 you can have your cake and eat it too:

    (defun has-non-nil (lst)
      (named-let loop ((lst lst))
        (cond
         ((null lst) nil)
         ((consp lst) (or (not (null (car lst))) (loop (cdr lst))))
         (t (error "Not a proper list! You cheater!")))))

Admittedly, here the `named-let` construct gives you only the
elimination of tail-recursion, but in many other circumstances it
also leads to quite elegant code.


        Stefan


PS: For the curious, here's what the above `named-let` expands to:

(defalias 'has-non-nil
  #'(lambda (lst)
      (let ((lst lst))
        (let (retval)
          (while
            (let ((lst lst))
              (cond
               ((null lst) nil)
               ((consp lst) (let ((val (not (null (car lst)))))
                              (if val (progn (setq retval val) nil)
                                (progn (setq lst (cdr lst)) :recurse))))
               (t (progn (setq retval (error "Not a proper list! You cheater!"))
                         nil)))))
          retval))))

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Michael Heerdegen]

Stefan Monnier via Users list for the GNU Emacs text editor
<help-gnu-emacs@gnu.org> writes:

> PS: For the curious, here's what the above `named-let` expands to:
>
> (defalias 'has-non-nil
>   #'(lambda (lst)
>       (let ((lst lst))
>         (let (retval)
>           (while
>             (let ((lst lst))
>               (cond
>                ((null lst) nil)
>                ((consp lst) (let ((val (not (null (car lst)))))
>                               (if val (progn (setq retval val) nil)
>                                 (progn (setq lst (cdr lst)) :recurse))))
>                (t (progn (setq retval (error "Not a proper list! You cheater!"))
>                          nil)))))
>           retval))))

Is that :recurse symbol only there to improve readability, or is it
handled specially?

Michael.

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[tomas]

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

On Fri, Oct 28, 2022 at 09:09:12AM -0400, Stefan Monnier via Users list for the GNU Emacs text editor wrote:
> Michael Heerdegen [2022-10-28 08:20:45] wrote:
> > <tomas@tuxteam.de> writes:
> >> If you are doing it "by hand", why not indulge in Lisp's
> >> "classic elegance", like so:

[...]

> > You don't want to implement such functions in Emacs with recursion
> > because you'll easily hit `max-lisp-eval-depth' when they are called.
> 
> Indeed (and it's significantly slower than the corresponding loop
> without function calls).

I /knew/ I was missing something. The back of my brain mumbled
"does Emacs have tail recursion elimination or doesn't it?"

> > Sorry to tell you, but a loop is the preferable way in Elisp.
> 
> Luckily, since Emacs-28 you can have your cake and eat it too:
> 
>     (defun has-non-nil (lst)
>       (named-let loop ((lst lst))
>         (cond
>          ((null lst) nil)
>          ((consp lst) (or (not (null (car lst))) (loop (cdr lst))))
>          (t (error "Not a proper list! You cheater!")))))

Thanks for that :)

> Admittedly, here the `named-let` construct gives you only the
> elimination of tail-recursion, but in many other circumstances it
> also leads to quite elegant code.

Now I think of it, I saw something flashing past emacs-devel; back
then I must have thought "oh, nice, I've got to play with this..."

Now it sank in. So thanks :)

Cheers
-- 
t

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

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

tomas wrote:

> If you are doing it "by hand", why not indulge in Lisp's
> "classic elegance", like so:
>
>   (defun has-non-nil (lst)
>     (cond
>      ((null lst) nil)
>      ((consp lst) (or (not (null (car lst))) (has-non-nil (cdr lst))))
>      (t (error "Not a proper list! You cheater!"))))

Did you mean: recursion

https://www.google.com/search?q=recursion

-- 
underground experts united
https://dataswamp.org/~incal

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Michael Heerdegen wrote:

>> If you are doing it "by hand", why not indulge in Lisp's
>> "classic elegance", like so:
>>
>>   (defun has-non-nil (lst)
>>     (cond
>>      ((null lst) nil)
>>      ((consp lst) (or (not (null (car lst))) (has-non-nil (cdr lst))))
>>      (t (error "Not a proper list! You cheater!"))))
>
> You don't want to implement such functions in Emacs with
> recursion because you'll easily hit `max-lisp-eval-depth'
> when they are called. Sorry to tell you, but a loop is the
> preferable way in Elisp.

He knows that ...
>
-- 
underground experts united
https://dataswamp.org/~incal

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Stefan Monnier via Users list for the GNU Emacs text editor]

> Is that :recurse symbol only there to improve readability, or is it
> handled specially?

It's just for readability.


        Stefan

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Stefan Monnier via Users list for the GNU Emacs text editor wrote:

>> You don't want to implement such functions in Emacs with
>> recursion because you'll easily hit `max-lisp-eval-depth'
>> when they are called.
>
> Indeed (and it's significantly slower than the corresponding
> loop without function calls).

Recursion is slower because of the continual function calls
and those will also blow the stack eventually ...

>> Sorry to tell you, but a loop is the preferable way
>> in Elisp.
>
> Luckily, since Emacs-28 you can have your cake and eat it too:
>
>     (defun has-non-nil (lst)
>       (named-let loop ((lst lst))
>         (cond
>          ((null lst) nil)
>          ((consp lst) (or (not (null (car lst))) (loop (cdr lst))))
>          (t (error "Not a proper list! You cheater!")))))

`named-let' is from a "[l]ooping construct taken from Scheme."

I love it that Elisp is like a "Lisp dump" area where
everything from the Lisp world worth having seems to end up
eventually ...

> Admittedly, here the `named-let` construct gives you only
> the elimination of tail-recursion, but in many other
> circumstances it also leads to quite elegant code.

Here tail refers to not the `cdr' of the list but the tail of
the function, "a tail call is a subroutine call performed as
the final action of a procedure. If the target of a tail is
the same subroutine, the subroutine is said to be tail
recursive, which is a special case of direct recursion" [1]

I don't know why that is such an important distinction, I also
remember recursion over trees that recursed both ways from the
top and middle nodes if it/they had several child nodes, so
I guess that recursion was both tail and direct LOL.

Elisp direct recursion example anyone?

And what was this continuation-passing style?

  CPS 1975 continuation-passing style, coined in "AI Memo 349"

I used it once, but don't remember what file that was ...

> (defalias 'has-non-nil
>   #'(lambda (lst) [...]

TIL: In Scheme-inspired Elisp, quoting lambdas is OK ...

[1] https://en.wikipedia.org/wiki/Tail_call

-- 
underground experts united
https://dataswamp.org/~incal

Re: [External] : Re: Testing whether a list contains at least one non-nil element

[Emanuel Berg]

Stefan Monnier via Users list for the GNU Emacs text editor wrote:

>> Is that :recurse symbol only there to improve readability,
>> or is it handled specially?
>
> It's just for readability.

Interesting ...

-- 
underground experts united
https://dataswamp.org/~incal