MAPCAR produces a new list as a result, right? While MAPCAN
'destructively' builds its result? I don't understand how they are
different....
CL-USER> (mapcar #'list '(1 2 3) '(2 4 6))
((1 2) (2 4) (3 6))
CL-USER> (mapcan #'list '(1 2 3) '(2 4 6))
(1 2 2 4 3 6)
CL-USER>
jmckitrick wrote:
> MAPCAR produces a new list as a result, right? While MAPCAN
> 'destructively' builds its result? I don't understand how they are
> different....
>
> CL-USER> (mapcar #'list '(1 2 3) '(2 4 6))
> ((1 2) (2 4) (3 6))
> CL-USER> (mapcan #'list '(1 2 3) '(2 4 6))
> (1 2 2 4 3 6)
> CL-USER>
Do those lists look the same to you? They look like pretty different
results to me.
The CLHS, believe it or not, is very helpful here:
"mapcan and mapcon are like mapcar and maplist respectively, except
that the results of applying function are combined into a list by the
use of nconc rather than list."
See the part about NCONC'ing the return values together? Funny what
you can find in the spec.
Questions like these (and many of your other posts) are probably better
asked in #lisp or with a little googling.
Bill Atkins wrote:
> Do those lists look the same to you? They look like pretty different
> results to me.
>
> The CLHS, believe it or not, is very helpful here:
>
> "mapcan and mapcon are like mapcar and maplist respectively, except
> that the results of applying function are combined into a list by the
> use of nconc rather than list."
>
> See the part about NCONC'ing the return values together? Funny what
> you can find in the spec.
It's not the literal effect I don't understand. It's if MAPCAN is
supposed to be the corresponding 'destructive' version of MAPCAR,
unless these two are not complimentary in that way.
Example:
CL-USER> (nconc '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
CL-USER> (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
CL-USER>
These produce the same result, but with different side effects. I
thought MAPCAR and MAPCAN had the same relationship, but that cannot
be, if the results are different.
Apparently, though, MAPCAN is not just a 'destructive' version of
MAPCAR. That's what I was trying to clarify.
jmckitrick wrote:
> Bill Atkins wrote:
> > Do those lists look the same to you? They look like pretty different
> > results to me.
> >
> > The CLHS, believe it or not, is very helpful here:
> >
> > "mapcan and mapcon are like mapcar and maplist respectively, except
> > that the results of applying function are combined into a list by the
> > use of nconc rather than list."
> >
> > See the part about NCONC'ing the return values together? Funny what
> > you can find in the spec.
>
> It's not the literal effect I don't understand. It's if MAPCAN is
> supposed to be the corresponding 'destructive' version of MAPCAR,
MAPCAN isn't a version of MAPCAR. It does something else: it assumes
that the function returns a list, and it catenates the lists together.
MAPCAN is a destructive version of a function which isn't in the
standard language. You can define that function yourself; one version
appears in Norvig's book, where it is called MAPPEND. MAPPEND catenates
the lists returned by the function as if by APPEND rather than NCONC.
> unless these two are not complimentary in that way.
>
> Example:
> CL-USER> (nconc '(1 2 3) '(4 5 6))
> (1 2 3 4 5 6)
> CL-USER> (append '(1 2 3) '(4 5 6))
Read what Bill Atkins pasted again: its' NCONC versus LIST, not NCONC
versus APPEND. MAPCAR works as if LIST were used to collect the
results, whereas MAPCAN works as if NCONC were used to catenate the
results.
> (1 2 3 4 5 6)
> CL-USER>
>
> These produce the same result, but with different side effects. I
> thought MAPCAR and MAPCAN had the same relationship, but that cannot
> be, if the results are different.
>
> Apparently, though, MAPCAN is not just a 'destructive' version of
> MAPCAR. That's what I was trying to clarify.
There cannot be a destructive version of MAPCAR in that sense, because
MAPCAR deals with items returned by the function, not with lists of
items. The function doesn't supply list structure to MAPCAR.
MAPCAR could be destructive in the sense that it operates on the
original list or lists that come into it. But that isn't the sense in
which MAPCAN is destructive; MAPCAN does not clobber the list(s) that
come into it.
"Kaz Kylheku" <········@gmail.com> writes:
>> Example:
>> CL-USER> (nconc '(1 2 3) '(4 5 6))
>> (1 2 3 4 5 6)
If you're lucky. It could as well explode.
(nconc (list 1 2 3) '(4 5 6))
on the other hand would work, but produce a "dangerous" results, half
mutable, half immutable...
(nconc (list 1 2 3) (list 4 5 6))
would produce a good, totally mutable result.
>> CL-USER> (append '(1 2 3) '(4 5 6))
produces the same half mutable, half immutable result as my first nconc above.
(append '(1 2 3) (list 4 5 6))
or:
(append '(1 2 3) '(4 5 6) nil)
would produce a good, totally mutable result.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Remember, Information is not knowledge; Knowledge is not Wisdom;
Wisdom is not truth; Truth is not beauty; Beauty is not love;
Love is not music; Music is the best." -- Frank Zappa
So let me get this right:
the reason
CL-USER> (mapcan #'+ (list 1 2 3) (list 4 5 6))
returns
9
is because the result of + does not return a list, so each success
iteration overwrites the result being accumulated, since there is no
cons cell in the result to attach to?
jmckitrick wrote:
> So let me get this right:
>
> the reason
>
> CL-USER> (mapcan #'+ (list 1 2 3) (list 4 5 6))
>
> returns
>
> 9
The ``Exceptional Situations'' paragraph for the MAP... functions says:
``Should be prepared to signal an error of type type-error if any list
is not a proper list.''
So the function is being misused.
> is because the result of + does not return a list, so each success
> iteration overwrites the result being accumulated, since there is no
> cons cell in the result to attach to?
More like, your implementation does not perform error checking, and in
failing to do so, it effectively ends up treating any atom, not only
NIL, as an empty list. All of these empty lists disappear in the
catenation except for the last one.
According to CL's definition of "dotted list", a lone atom isn't a
dotted list. However, it can algorithmically be treated as if it were
one.
"jmckitrick" <···········@yahoo.com> writes:
> So let me get this right:
>
> the reason
>
> CL-USER> (mapcan #'+ (list 1 2 3) (list 4 5 6))
>
> returns
>
> 9
>
> is because the result of + does not return a list, so each success
> iteration overwrites the result being accumulated, since there is no
> cons cell in the result to attach to?
I wouldn't count on it. As I read CLHS, this behavior is nice but
not conformant.
mapcan and mapcon are like mapcar and maplist respectively, except that the
results of applying function are combined into a list by the use of nconc
rather than list. That is,
(mapcon f x1 ... xn)
== (apply #'nconc (maplist f x1 ... xn))
and similarly for the relationship between mapcan and mapcar.
[131]> (nconc 5 7 9)
*** - NCONC: 7 is not a list
nconc &rest lists => concatenated-list
Arguments and Values:
list---each but the last must be a list (which might be a dotted
list but must not be a circular list); the last list may be any
object.
--
__Pascal Bourguignon__ http://www.informatimago.com/
This universe shipped by weight, not volume. Some expansion may have
occurred during shipment.
Le Fri, 18 Aug 2006 16:52:17 +0200, Pascal Bourguignon a écrit :
>> CL-USER> (mapcan #'+ (list 1 2 3) (list 4 5 6))
>>
>> returns
>>
>> 9
>
> I wouldn't count on it. As I read CLHS, this behavior is nice but
> not conformant.
That's a problem: cmucl 19c, clisp 2.38 and sbcl 0.9.14.0 all exhibit
this behaviour... Are you sure it isn't conformant?
Is there a relevant test in any of the publicly available conformance
test suites?
Curiously,
Nowhere man
--
···········@levallois.eu.org
OpenPGP 0xD9D50D8A
Pierre THIERRY <···········@levallois.eu.org> writes:
> Le Fri, 18 Aug 2006 16:52:17 +0200, Pascal Bourguignon a �crit�:
>>> CL-USER> (mapcan #'+ (list 1 2 3) (list 4 5 6))
>>>
>>> returns
>>>
>>> 9
>>
>> I wouldn't count on it. As I read CLHS, this behavior is nice but
>> not conformant.
>
> That's a problem: cmucl 19c, clisp 2.38 and sbcl 0.9.14.0 all exhibit
> this behaviour... Are you sure it isn't conformant?
From the wording of the specification, I'd expect an error signaled,
since that's what NCONS must do.
> Is there a relevant test in any of the publicly available conformance
> test suites?
--
__Pascal Bourguignon__ http://www.informatimago.com/
Cats meow out of angst
"Thumbs! If only we had thumbs!
We could break so much!"
jmckitrick wrote:
> It's not the literal effect I don't understand. It's if MAPCAN is
> supposed to be the corresponding 'destructive' version of MAPCAR,
> unless these two are not complimentary in that way.
>
> Example:
> CL-USER> (nconc '(1 2 3) '(4 5 6))
> (1 2 3 4 5 6)
> CL-USER> (append '(1 2 3) '(4 5 6))
> (1 2 3 4 5 6)
> CL-USER>
>
> These produce the same result, but with different side effects. I
> thought MAPCAR and MAPCAN had the same relationship, but that cannot
> be, if the results are different.
>
> Apparently, though, MAPCAN is not just a 'destructive' version of
> MAPCAR. That's what I was trying to clarify.
Think of it this way: the application (mapcar fn list) calls fn with
the car of each successive cons in list. (maplist fn list) calls fn on
list and then the cdr of each successive cons in list.
In the same way, MAPCAN passes one item to FN, exactly as MAPCAR would.
MAPCON passes a list, exactly as MAPLIST would. Clearer?
"jmckitrick" <···········@yahoo.com> writes:
> Bill Atkins wrote:
>> Do those lists look the same to you? They look like pretty different
>> results to me.
>>
>> The CLHS, believe it or not, is very helpful here:
>>
>> "mapcan and mapcon are like mapcar and maplist respectively, except
>> that the results of applying function are combined into a list by the
>> use of nconc rather than list."
>>
>> See the part about NCONC'ing the return values together? Funny what
>> you can find in the spec.
>
> It's not the literal effect I don't understand. It's if MAPCAN is
> supposed to be the corresponding 'destructive' version of MAPCAR,
> unless these two are not complimentary in that way.
>
> Example:
> CL-USER> (nconc '(1 2 3) '(4 5 6))
> (1 2 3 4 5 6)
> CL-USER> (append '(1 2 3) '(4 5 6))
> (1 2 3 4 5 6)
> CL-USER>
>
> These produce the same result, but with different side effects. I
> thought MAPCAR and MAPCAN had the same relationship, but that cannot
> be, if the results are different.
>
> Apparently, though, MAPCAN is not just a 'destructive' version of
> MAPCAR. That's what I was trying to clarify.
Just ask it! ;-)
(setf *print-circle* t)
(let ((as (list 'one 'two 'three))
(bs (list 'un 'deux 'trois))
(cared-objects '())
(caned-objects '()))
(let ((mapcar-result (mapcar (lambda (a b)
(let ((object (list a b)))
(push object cared-objects)
object))
as bs))
(mapcan-result (mapcan (lambda (a b)
(let ((object (list a b)))
(push object caned-objects)
object))
as bs)))
(setf cared-objects (nreverse cared-objects)
caned-objects (nreverse caned-objects))
(list
`(as ,as)
`(bs ,bs)
`(cared-objects ,cared-objects)
`(mapcar-result ,mapcar-result)
`(caned-objects ,caned-objects)
`(mapcan-result ,mapcan-result))))
-->
((AS (ONE TWO THREE))
(BS (UN DEUX TROIS))
(CARED-OBJECTS (#1=(ONE UN) #2=(TWO DEUX) #3=(THREE TROIS)))
(MAPCAR-RESULT (#1# #2# #3#))
(CANED-OBJECTS (#4=(ONE UN . #5=(TWO DEUX . #6=(THREE TROIS))) #5# #6#))
(MAPCAN-RESULT #4#))
With *print-circle*, any non-symbol object that appears several times
in the s-expr is first identified with #N= and then referenced with
#N#. You can then see where the same CONS cell is referenced twice
(or more). (interned symbols printed identically are identical by
definition, so there's no need to number them).
In the mapcar part, you see that each of the objects returned by the
lambda #1#, #2# and #3# are collected in a new list created and
returned by mapcar (no other references to the CONS cells of this list
exist anywhere else).
In the mapcan part, on the contrary you see that the CONS cells of the
list returned by mapcan are actually the CONS cells returned by the
lambda.
The first object put on the caned-objects list was #4=(ONE . (UN . NIL))
The second object put on the caned-objects list was #5=(TWO . (DEUX . NIL))
When this second object was returned by the lambda, MAPCAN modified
the CDR of the LAST cell of the first object #4#, doing something like:
(setf (cdr (last #4#)) #5#)
Hence, now you see that #4# include #5#:
#4=(ONE . (UN . #5=(TWO . (DEUX . NIL))))
The third object put on the caned-object list was #6#, and when
returned, has been assigned by MAPCAN to the CDR of the new LAST
cell, of the object #5#:
(setf (cdr (last #4#)) #6#)
Hence, now you see that #4# include #5#:
#4=(ONE . (UN . #5=(TWO . (DEUX . #6=(THREE . (TROIS . NIL))))))
or:
#4=(ONE UN . #5=(TWO DEUX . #6=(THREE TROIS)))
as the printer puts it. Finally, this is this list that is returned
by MAPCAN. MAPCAN didn't CONS any list. It modified the lists it got
from the lambda, and concatenated them into one big list.
Exercise: draw a diagram of boxes and arrows representing the whole result:
((AS (ONE TWO THREE))
(BS (UN DEUX TROIS))
(CARED-OBJECTS (#1=(ONE UN) #2=(TWO DEUX) #3=(THREE TROIS)))
(MAPCAR-RESULT (#1# #2# #3#))
(CANED-OBJECTS (#4=(ONE UN . #5=(TWO DEUX . #6=(THREE TROIS))) #5# #6#))
(MAPCAN-RESULT #4#))
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You can tell the Lisp programmers. They have pockets full of punch
cards with close parentheses on them." --> http://tinyurl.com/8ubpf
On 2006-08-17 16:07:53 +0100, "jmckitrick" <···········@yahoo.com> said:
> It's not the literal effect I don't understand. It's if MAPCAN is
> supposed to be the corresponding 'destructive' version of MAPCAR,
> unless these two are not complimentary in that way.
It's not a destructive equivalent of MAPCAR in the way you probably
think it is - there *is* no destructive equivalent of MAPCAR in that
sense (what would one do?). What the spec means is that it maps over
its arguments in the same way MAPCAR does - by picking successive
elements - rather than like MAPLIST does - by picking successive tails.
MAPCAN is terribly useful when you want to collect only some things:
(defun find-interesting (huge-list)
(mapcan #'(lambda (e) (if (interestingp e) (list e) nil)) huge-list))
--tim (and that's the first Lisp I've written for nearly 2 years!)
Tim Bradshaw wrote:
> On 2006-08-17 16:07:53 +0100, "jmckitrick" <···········@yahoo.com> said:
>
>> It's not the literal effect I don't understand. It's if MAPCAN is
>> supposed to be the corresponding 'destructive' version of MAPCAR,
>> unless these two are not complimentary in that way.
>
>
> It's not a destructive equivalent of MAPCAR in the way you probably
> think it is - there *is* no destructive equivalent of MAPCAR in that
> sense (what would one do?). What the spec means is that it maps over
> its arguments in the same way MAPCAR does - by picking successive
> elements - rather than like MAPLIST does - by picking successive tails.
IIRC, Graham illustrates macrology with a MAPPEND implementation.
>
> MAPCAN is terribly useful when you want to collect only some things:
>
> (defun find-interesting (huge-list)
> (mapcan #'(lambda (e) (if (interestingp e) (list e) nil)) huge-list))
ick.
(loop for e in huge-list when (interestingp e) collect e)
>
> --tim (and that's the first Lisp I've written for nearly 2 years!)
Still rebuilding after the weight of all those Java references collapsed
the home?
:)
kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
On 2006-08-17 20:39:00 +0100, Ken Tilton <·········@gmail.com> said:
>>
>> MAPCAN is terribly useful when you want to collect only some things:
>>
>> (defun find-interesting (huge-list)
>> (mapcan #'(lambda (e) (if (interestingp e) (list e) nil)) huge-list))
>
> ick.
>
> (loop for e in huge-list when (interestingp e) collect e)
Well, sure.
>
>>
>> --tim (and that's the first Lisp I've written for nearly 2 years!)
>
> Still rebuilding after the weight of all those Java references
> collapsed the home?
No, I find Java fine for what I use it for (for instance generating
hand-crafted syslog packets or something). I just don't really write
programs any more, I `architect security solutions' or some such
bullshit. I'm sure I'd use Lisp if I did program.
--tim
"jmckitrick" <···········@yahoo.com> writes:
> MAPCAR produces a new list as a result, right? While MAPCAN
> 'destructively' builds its result? I don't understand how they are
> different....
>
> CL-USER> (mapcar #'list '(1 2 3) '(2 4 6))
> ((1 2) (2 4) (3 6))
> CL-USER> (mapcan #'list '(1 2 3) '(2 4 6))
> (1 2 2 4 3 6)
Well, it's easy, mapcar list returns: ((1 2) (2 4) (3 6))
and mapcan list returns: (1 2 2 4 3 6)
That's how they're different.
If you still don't understand, an easy way to see it, is to read the
CLHS and try to implement (a simplified version) of each of the
functions.
For example, if we restrict ourself to one list, and don't care for
the abysmal performances:
(defun MAPCAR (fun list)
(if (null list)
'()
(CONS (funcall fun (car list)) (MAPCAR fun (cdr list)))))
(defun MAPCAN (fun list)
(if (null list)
'()
(NCONC (funcall fun (car list)) (MAPCAN fun (cdr list)))))
Of course, you'd better understand the difference between CONS and NCONC...
(read CLHS)
--
__Pascal Bourguignon__ http://www.informatimago.com/
HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.