Stats

  • Locked Locked
  • Replies 11
  • Subscribers 144
  • Views 4491
  • 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:

    Hey wait a minute--shouldn't mapcan use tconc internally rather than nconc?

    It doesn't do either. It keeps track of the end of the list as it goes along - so there's no need to actually store it in a tconc structure. It certainly doesn't use nconc.

    [/quote]

    The reference manual lied to me!

    mapcan

    mapcan(u_funcl_arg1[ l_arg2 ... ])=> l_result

    Description

    Applies a function to successive elements of the argument lists and returns the result of appending these intermediate results. All of the lists should have the same length.

    Specifically, a function is applied to the car of all the argument lists, passed in the same order as the argument lists. The second elements are processed next, continuing until the last element is processed. The result of each call to u_func must be a list. These lists are concatenated using nconc and the resulting list of all the concatenations is the result of mapcan. The argument u_func must accept as many arguments as there are lists.

Reply

  • Andrew Beckett said:

    Hey wait a minute--shouldn't mapcan use tconc internally rather than nconc?

    It doesn't do either. It keeps track of the end of the list as it goes along - so there's no need to actually store it in a tconc structure. It certainly doesn't use nconc.

    [/quote]

    The reference manual lied to me!

    mapcan

    mapcan(u_funcl_arg1[ l_arg2 ... ])=> l_result

    Description

    Applies a function to successive elements of the argument lists and returns the result of appending these intermediate results. All of the lists should have the same length.

    Specifically, a function is applied to the car of all the argument lists, passed in the same order as the argument lists. The second elements are processed next, continuing until the last element is processed. The result of each call to u_func must be a list. These lists are concatenated using nconc and the resulting list of all the concatenations is the result of mapcan. The argument u_func must accept as many arguments as there are lists.

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.