How to mapcar or across a list?

How to mapcar or across a list?

[Marcin Borkowski]

Hi there,

so here's my problem: I have a list of Boolean values, and I want to
`mapcar' an `or' across it (IOW, I want to test whether at least one of
them is true).  Of course, (apply #'or my-list) does not work.  Of
course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
there a better method?

BTW, my-list doesn't really exist: it is a result of `mapcar'ing
a function taking some value and yielding a Boolean value, so bonus
points if the method does not process the whole list.

(Note: I just noticed that my-list is in fact sorted so that all true
values (if any) will occur at the beginning anyway, so I can just test
the first one.  This means that my problem is purely academic, though
still interesting, I guess.)

Best,

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

Re: How to mapcar or across a list?

[Rasmus]

Marcin Borkowski <mbork@mbork.pl> writes:

> Hi there,
>
> so here's my problem: I have a list of Boolean values, and I want to
> `mapcar' an `or' across it (IOW, I want to test whether at least one of
> them is true).  Of course, (apply #'or my-list) does not work.  Of
> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
> there a better method?
>
> BTW, my-list doesn't really exist: it is a result of `mapcar'ing
> a function taking some value and yielding a Boolean value, so bonus
> points if the method does not process the whole list.

Does cl-some and cl-every fit the bill?

Rasmus

-- 
Vote for Dick Taid in an election near you!

Re: How to mapcar or across a list?

[Pascal J. Bourguignon]

Marcin Borkowski <mbork@mbork.pl> writes:

> Hi there,
>
> so here's my problem: I have a list of Boolean values, and I want to
> `mapcar' an `or' across it (IOW, I want to test whether at least one of
> them is true).  Of course, (apply #'or my-list) does not work.  Of
> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
> there a better method?
>
> BTW, my-list doesn't really exist: it is a result of `mapcar'ing
> a function taking some value and yielding a Boolean value, so bonus
> points if the method does not process the whole list.

It's too late, lisp is not a lazy language.

> (Note: I just noticed that my-list is in fact sorted so that all true
> values (if any) will occur at the beginning anyway, so I can just test
> the first one.  This means that my problem is purely academic, though
> still interesting, I guess.)

First you want to reduce a list of booleans to a single value, so what
makes you thing that mapcar is the right too for that?  There's the word
"map" in "mapcar", didn't you notice?

       map           reduce

    x1 --> r1       x1 -\
    x2 --> r2       x2 --+-> r
    x3 --> r3       x3 -/

Also, mapcar allocates a new list of same length as the original list
for the result, so it is costly.  At least, you could consider mapc.



With mapc (or mapcar) you could perform your task with some cl magic:

    (require 'cl)
    (setf lexical-binding t)

    (defun* or-all (list)
       (mapc (lambda (element)
                (when element
                  (return-from or-all t)))
             list)
       nil)

    (defun* and-all (list)
       (mapc (lambda (element)
                (unless element
                  (return-from and-all nil)))
             list)
       t)

    (or-all '(nil nil nil)) --> nil
    (or-all '(nil t   nil)) --> t 

    (and-all '(t   t   t)) --> t
    (and-all '(t   nil t)) --> nil 


But I fail to see how it's better than:

    (defun* or-all (list)
       (reduce (lambda (a b) (or a b)) list))

    (defun* and-all (list)
       (reduce (lambda (a b) (and a b)) list))


or than just:

   (some     'identity '(nil nil nil)) --> nil
   (some     'identity '(nil t   nil)) --> t
   (some     'identity '(t   t   t  )) --> t

   (every    'identity '(nil nil nil)) --> nil
   (every    'identity '(t   nil t  )) --> nil 
   (every    'identity '(t   t   t  )) --> t

There are also the negations:

   (notevery 'identity '(nil nil nil)) --> t
   (notevery 'identity '(nil t   nil)) --> t
   (notevery 'identity '(t   t   t  )) --> nil

   (notany   'identity '(nil nil nil)) --> t
   (notany   'identity '(t   nil t  )) --> nil 
   (notany   'identity '(t   t   t  )) --> nil


And since your booleans are computed by a function with mapcar, you
could avoid computing this function for all the elements of the original
list, and you could avoid allocating the temporary list by having some
call this function:


So instead of:

    (reduce (lambda (a b) (or a b))
            (mapcar 'complex-and-lengthy-predicate list))

use:

    (some 'complex-and-lengthy-predicate list)



For example:
    (some (lambda (x) (print x) (evenp x)) '(1 2 3 5 7 9 11))
prints:
    1

    2
--> t


Learn more about Common Lisp:
http://www.lispworks.com/documentation/HyperSpec/Front/
http://cliki.net/

-- 
__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 mapcar or across a list?

[Marcin Borkowski]

On 2015-07-15, at 22:42, Rasmus <rasmus@gmx.us> wrote:

> Marcin Borkowski <mbork@mbork.pl> writes:
>
>> Hi there,
>>
>> so here's my problem: I have a list of Boolean values, and I want to
>> `mapcar' an `or' across it (IOW, I want to test whether at least one of
>> them is true).  Of course, (apply #'or my-list) does not work.  Of
>> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
>> there a better method?
>>
>> BTW, my-list doesn't really exist: it is a result of `mapcar'ing
>> a function taking some value and yielding a Boolean value, so bonus
>> points if the method does not process the whole list.
>
> Does cl-some and cl-every fit the bill?

Ha.  Their only drawback is that I didn't know about them...

> Rasmus

Thanks!

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

Re: How to mapcar or across a list?

[Marcin Borkowski]

On 2015-07-15, at 22:45, Pascal J. Bourguignon <pjb@informatimago.com> wrote:

> Marcin Borkowski <mbork@mbork.pl> writes:
>
>> Hi there,
>>
>> so here's my problem: I have a list of Boolean values, and I want to
>> `mapcar' an `or' across it (IOW, I want to test whether at least one of
>> them is true).  Of course, (apply #'or my-list) does not work.  Of
>> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
>> there a better method?
>>
>> BTW, my-list doesn't really exist: it is a result of `mapcar'ing
>> a function taking some value and yielding a Boolean value, so bonus
>> points if the method does not process the whole list.
>
> It's too late, lisp is not a lazy language.

Well, *after* I mapcar then it's too late, but your own answer (below)
shows that mapcar itself is not necessary (as I suspected).

>> (Note: I just noticed that my-list is in fact sorted so that all true
>> values (if any) will occur at the beginning anyway, so I can just test
>> the first one.  This means that my problem is purely academic, though
>> still interesting, I guess.)
>
> First you want to reduce a list of booleans to a single value, so what
> makes you thing that mapcar is the right too for that?  There's the word
> "map" in "mapcar", didn't you notice?

My bad, you're right, of course.

>        map           reduce
>
>     x1 --> r1       x1 -\
>     x2 --> r2       x2 --+-> r
>     x3 --> r3       x3 -/

Please, do not shame a mathematician.  I hope notany (pun intended;-))
of my students will read this...

> Also, mapcar allocates a new list of same length as the original list
> for the result, so it is costly.  At least, you could consider mapc.

True.

> With mapc (or mapcar) you could perform your task with some cl magic:
>
>     (require 'cl)
>     (setf lexical-binding t)
>
>     (defun* or-all (list)
>        (mapc (lambda (element)
>                 (when element
>                   (return-from or-all t)))
>              list)
>        nil)
>
>     (defun* and-all (list)
>        (mapc (lambda (element)
>                 (unless element
>                   (return-from and-all nil)))
>              list)
>        t)
>
>     (or-all '(nil nil nil)) --> nil
>     (or-all '(nil t   nil)) --> t 
>
>     (and-all '(t   t   t)) --> t
>     (and-all '(t   nil t)) --> nil 
>
>
> But I fail to see how it's better than:
>
>     (defun* or-all (list)
>        (reduce (lambda (a b) (or a b)) list))
>
>     (defun* and-all (list)
>        (reduce (lambda (a b) (and a b)) list))

Of course, but - as I expected - someone already felt that there should
be a more elegant way, and hence the abstraction called `some', `every' etc.

> or than just:
>
>    (some     'identity '(nil nil nil)) --> nil
>    (some     'identity '(nil t   nil)) --> t
>    (some     'identity '(t   t   t  )) --> t
>
>    (every    'identity '(nil nil nil)) --> nil
>    (every    'identity '(t   nil t  )) --> nil 
>    (every    'identity '(t   t   t  )) --> t
>
> There are also the negations:
>
>    (notevery 'identity '(nil nil nil)) --> t
>    (notevery 'identity '(nil t   nil)) --> t
>    (notevery 'identity '(t   t   t  )) --> nil
>
>    (notany   'identity '(nil nil nil)) --> t
>    (notany   'identity '(t   nil t  )) --> nil 
>    (notany   'identity '(t   t   t  )) --> nil
>
> And since your booleans are computed by a function with mapcar, you
> could avoid computing this function for all the elements of the original
> list, and you could avoid allocating the temporary list by having some
> call this function:
>
>
> So instead of:
>
>     (reduce (lambda (a b) (or a b))
>             (mapcar 'complex-and-lengthy-predicate list))
>
> use:
>
>     (some 'complex-and-lengthy-predicate list)

How cool.  Again: I felt that something like that should exist, so I'm
not surprised that it actually does.

> For example:
>     (some (lambda (x) (print x) (evenp x)) '(1 2 3 5 7 9 11))
> prints:
>     1
>
>     2
> --> t
>
>
> Learn more about Common Lisp:
> http://www.lispworks.com/documentation/HyperSpec/Front/
> http://cliki.net/

Well, maybe I should.  I have a bunch of students who want to study CL,
I should be able to help them;-).  (I read parts of the Cl spec, most of
"Practical Common Lisp" and small parts of "On Lisp", but that was a few
years ago...)

Thanks again,

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

Re: How to mapcar or across a list?

[Emanuel Berg]

Marcin Borkowski <mbork@mbork.pl> writes:

> so here's my problem: I have a list of Boolean
> values, and I want to `mapcar' an `or' across it
> (IOW, I want to test whether at least one of them is
> true). Of course, (apply #'or my-list) does not
> work. Of course, I can (cl-reduce (lambda (x y) (or
> x y)) my-list) -- but is there a better method?

"Better" I don't know, but how about using your
new-found skills with the backquote? (`or' itself
should be used, of course.)

    (setq boolean-list-1 '(t   nil nil nil t   nil nil))
    (setq boolean-list-2 '(nil nil nil nil nil nil nil))

    (eval `(or ,@boolean-list-1)) ; t
    (eval `(or ,@boolean-list-2)) ; nil

> BTW, my-list doesn't really exist: it is a result of
> `mapcar'ing a function taking some value and
> yielding a Boolean value, so bonus points if the
> method does not process the whole list.

Check. It is a consequence of using `or', which is
"short circuited" as it is called in other languages,
perhaps in Lisp too - I've read
"conditional evaluation" as well in AI books, but
perhaps that is something else.

Anyway:

    (or t undefined) ; t
    (or undefined t) ; error: (void-variable undefined) in eval

To verify, append "undefined" to "boolean-list-1"
(no error) - but, there will be an error (the same as
above) if appended to "boolean-list-2"!

... I suppose now would be a good time for you to hand
over them points!

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

Re: How to mapcar or across a list?

[John Mastro]

> so here's my problem: I have a list of Boolean values, and I want to
> `mapcar' an `or' across it (IOW, I want to test whether at least one of
> them is true).  Of course, (apply #'or my-list) does not work.  Of
> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
> there a better method?

You've already gotten good answers from others but, for the sake of one
more option, you could also accomplish this with `cl-loop' (which, of
course, some love and some hate).

It would end up looking something like:

(cl-loop for item in list
         thereis (your-predicate item))

If the predicate would be `(not (null item))', you can drop it entirely
(as you would expect):

(cl-loop for item in list thereis item)

-- 
john

Re: How to mapcar or across a list?

[Pascal J. Bourguignon]

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

> Marcin Borkowski <mbork@mbork.pl> writes:
>
>> so here's my problem: I have a list of Boolean
>> values, and I want to `mapcar' an `or' across it
>> (IOW, I want to test whether at least one of them is
>> true). Of course, (apply #'or my-list) does not
>> work. Of course, I can (cl-reduce (lambda (x y) (or
>> x y)) my-list) -- but is there a better method?
>
> "Better" I don't know, but how about using your
> new-found skills with the backquote? (`or' itself
> should be used, of course.)
>
>     (setq boolean-list-1 '(t   nil nil nil t   nil nil))
>     (setq boolean-list-2 '(nil nil nil nil nil nil nil))
>
>     (eval `(or ,@boolean-list-1)) ; t
>     (eval `(or ,@boolean-list-2)) ; nil

Nope.  

It's always a bad idea to use eval, because eval evalutes in the nil
environment, not in the local lexical envrionment.

Your example works because those lists are literal, but then you don't
need or to know the answer.

In pratice, translating:

   (flet ((some-complex-predicate (x) …))
     (let ((some-data (generate-some-data)))
        (some (function some-complex-predicate) some-data)))

to:

   (flet ((some-complex-predicate (x) …))
     (let ((some-data (generate-some-data)))
       (eval `(or ,@(mapcar (lambda (data)
                               `(some-complex-predicate ',data))
                            some-data)))))

fails lamentably.  

It is also very slow, since it makes you build a new list,
and it makes you interpret, or worse, compile, some new code!

-- 
__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 mapcar or across a list?

[Emanuel Berg]

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

> It's always a bad idea to use eval, because eval
> evalutes in the nil environment, not in the local
> lexical envrionment.
>
> Your example works because those lists are literal,
> but then you don't need or to know the answer.

OK, what about doing `cl-dolist' which we also had in
a recent discussion?

    (cl-dolist (b boolean-list-1) (when b (cl-return t))) ; t
    (cl-dolist (b boolean-list-2) (when b (cl-return t))) ; nil

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

Re: How to mapcar or across a list?

[Barry Margolin]

In article <mailman.6968.1436991281.904.help-gnu-emacs@gnu.org>,
 Marcin Borkowski <mbork@mbork.pl> wrote:

> Hi there,
> 
> so here's my problem: I have a list of Boolean values, and I want to
> `mapcar' an `or' across it (IOW, I want to test whether at least one of
> them is true).  Of course, (apply #'or my-list) does not work.  Of
> course, I can (cl-reduce (lambda (x y) (or x y)) my-list) -- but is
> there a better method?

"mapcar" is not the right metaphor. It's for running the same function 
separately on each element of a list, not for combining elements.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***