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

  • 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.

    mapcan, like most destructive functions, can definitely be useful if care is taken because of the side effects. If you can guarantee that the return value of the function is a new (non-shared) list, then it is safe and advantageous to use. Because there are relatively few destructive functions, it doesn't take much effort to look for potential bugs like this.

    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. 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.

    Note I didn't do any profiling of this to check.

    Andrew.

Reply

  • 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.

    mapcan, like most destructive functions, can definitely be useful if care is taken because of the side effects. If you can guarantee that the return value of the function is a new (non-shared) list, then it is safe and advantageous to use. Because there are relatively few destructive functions, it doesn't take much effort to look for potential bugs like this.

    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. 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.

    Note I didn't do any profiling of this to check.

    Andrew.

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.