Stats

  • Locked Locked
  • Replies 11
  • Subscribers 144
  • Views 4492
  • Members are here 0
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

nconc with (back)quote'd list constants

tweeks

Google says: "Avoid nconc!"

http://google-styleguide.googlecode.com/svn/trunk/lispguide.xml#Avoid_NCONC

They recommend to use "mappend" instead, which you could naively define this way (naive because it's O(n^2)!):

(defun mappend (fn list "ul")
  "Append the results of calling fn on each element of list.
  Like mapcan, but uses append instead of nconc."
  (foldl1 append (mapcar fn list)))

(defun foldl1 (function list "ul")
  (if (null list)
      (error "foldl1: empty list")
      (foldl function (car list) (cdr list))))

(defun foldl (function initial list "ugl")
  (let ((result initial))
    (foreach mapc element list
      (setq result (function result element)))
    result))

If you don't see the danger, try this:

ILS-> (mappend (lambda (x) '(t)) '(1 2 3))
(t t t)
ILS-> (mapcan (lambda (x) '(t)) '(1 2 3))

The mappend version works correctly, but the mapcan version sends the interpreter into an infinite loop! 

Explanation: mapcan applies the lambda to 1, and nconcs the result--the constant '(t) list returned by the lambda--to itself, resulting in a circular list of length one, where the car is t and the cdr is its own car.  The next iteration, mapcan applies the lambda to 2, only this time nconc never returns, because it's too busy trying to find the end of an endless list....

I guess I'll have to write my own (foreach mappend....) to use in place of the more dangerous (foreach mapcan...).

Parents

  •  

    Andrew Beckett said:

    Potentially you could just do:

    (defun CCFmappend (func @rest lists)
      (apply 'mapcan (lambda (@rest args) (copy (apply func args))) lists))

    which generalizes it to multiple lists, and uses copy to guarantee a unique list.

    Thanks Andrew!  I had not thought of using copy, which I think is rather brilliant.

    Andrew Beckett said:

    If you can guarantee that the list in your mapping function isn't shared though, it's not needed and you can save a little time and garbage - although it's only going to generate as much garbage as the length of the final list in that case, so the savings may not be worth it.

    Yeah, it's a relatively small penalty for me since my lists are usually small.  Then again, I've used mapcan for years, and only perhaps once or twice have I ever run into this stale-list problem.  Maybe a better solution is to prefer consing fresh lists to using quoted constants?

     Ah, I still remember that fateful day when I discovered that a caller can modify a quoted constant list inside a procedure.... 

    ILS-> (defun foo () '(1 2 3))
foo
ILS-> (remd 2 (foo))
(1 3)
ILS-> (foo)
(1 3)
ILS-> pp(foo)
(procedure (foo)
    (quote 
	(1 3)
    )
)
nil

    Totally blew my mind. :)

    Andrew Beckett said:

    Whilst I agree to some extent with the sentiment of avoiding nconc, I'm not sure I agree that using mappend (as you've implemented it) is a good idea. The point that the style guide is trying to make, I think, is that if you are doing one-off nconcs to gain performance/memory utilization benefits over append, then it's not worth it. If however you're doing repeated nconcs rather than appends, then really you are approaching the problem the wrong way - repeated nconcs and appends are both bad because they both have to traverse the first list to find the end - so as the list gets longer they take more time. nconc saves copying the second list, but it doesn't save the time to reach the end of the first list. Your mappend is simply calling append repeatedly - doing this with nconc is (almost) as bad.

    One thing SKILL has which I have not yet found in Common Lisp is tconc and lconc.  Do you think it would be even more efficient to define CCFmappend in terms of tconc and lconc rather than mapcan? 

Reply

  •  

    Andrew Beckett said:

    Potentially you could just do:

    (defun CCFmappend (func @rest lists)
      (apply 'mapcan (lambda (@rest args) (copy (apply func args))) lists))

    which generalizes it to multiple lists, and uses copy to guarantee a unique list.

    Thanks Andrew!  I had not thought of using copy, which I think is rather brilliant.

    Andrew Beckett said:

    If you can guarantee that the list in your mapping function isn't shared though, it's not needed and you can save a little time and garbage - although it's only going to generate as much garbage as the length of the final list in that case, so the savings may not be worth it.

    Yeah, it's a relatively small penalty for me since my lists are usually small.  Then again, I've used mapcan for years, and only perhaps once or twice have I ever run into this stale-list problem.  Maybe a better solution is to prefer consing fresh lists to using quoted constants?

     Ah, I still remember that fateful day when I discovered that a caller can modify a quoted constant list inside a procedure.... 

    ILS-> (defun foo () '(1 2 3))
foo
ILS-> (remd 2 (foo))
(1 3)
ILS-> (foo)
(1 3)
ILS-> pp(foo)
(procedure (foo)
    (quote 
	(1 3)
    )
)
nil

    Totally blew my mind. :)

    Andrew Beckett said:

    Whilst I agree to some extent with the sentiment of avoiding nconc, I'm not sure I agree that using mappend (as you've implemented it) is a good idea. The point that the style guide is trying to make, I think, is that if you are doing one-off nconcs to gain performance/memory utilization benefits over append, then it's not worth it. If however you're doing repeated nconcs rather than appends, then really you are approaching the problem the wrong way - repeated nconcs and appends are both bad because they both have to traverse the first list to find the end - so as the list gets longer they take more time. nconc saves copying the second list, but it doesn't save the time to reach the end of the first list. Your mappend is simply calling append repeatedly - doing this with nconc is (almost) as bad.

    One thing SKILL has which I have not yet found in Common Lisp is tconc and lconc.  Do you think it would be even more efficient to define CCFmappend in terms of tconc and lconc rather than mapcan? 

Children
No Data

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.