<clip> Here are my archives. Cheers. Marco ---------------------------------------------------------------- Hi again Michael, Here's how DELIST works(using previous data list): As posted 11:47AM (delist lst) (0 1 2 (3 . 4) (5 6) ((7 8) (9 10 11 12)) (((13 . 14) (15 16) (17 . 18) As posted 11:59 AM (delist lst) (0 1 2 (3 . 4) (5 6) ((7 8) (9 10 11 12)) (((13 . 14) (15 16) (17 . 18) (19 20))) 21) The main problem with IF's, is the task of visually finding the ELSE's(especially when NIL is implicity rather than explicitly returned), and also spotting the end of the if(even when well nested). If well commented, IF's are still readable. I don't think, however, that nested IF's are necessarily any faster than COND, since IF (check me here) was not initially a root LISP function. There are certain problems that are naturals for nested IF's however. I explain how my second function worked (for the benefit of others, NOT RRB, MP, and BJ) who may not understand recursion.) (copied from my 2nd post for illustration here): ;;D. C. Broad, Jr. 10/25/02 (defun flatten (l) (cond ((null l) nil) ((atom l) (list l)) ((atom (car l)) (cons (car l) (flatten (cdr l)))) ((append (flatten (car l))(flatten (cdr l)))) )) ;|This function is a pure recursive algorithm, rather than an iterative one. Due to the generally recursive nature of lists, I discarded the notion that I could solve it (as simply) by iteration. Generally iteration is faster. Simplicity in the coding is beneficial during both creation and maintainance. |COND is a function that I greatly appreciate. Its arguments are lists of the form (<test expression> [<do expressions>]). COND evaluates the lists in order and does not evaluate the lists following the first <test expression> that is non-NIL. 1. Recursive algorithms should first check the end condition: NIL If found, they should return NIL. This begins the reverse assembly as the return values collect and forms the end of the LIST. 2. The next check determines whether the argument is just an ATOM and not a list. The NIL check must come first, since (ATOM NIL) -> T. Since flatten is primarily building the right side of the list and will arrive at the next level up into an append function, the return value must be a list instead of an atom. If this is not a nested call, but instead the top level event, it will turn an ATOM argument into a LIST. 3. The next check avoids unnecessary APPEND calls, (which being relatively slow, adversly affected my first algorithm). If the first element of the list is just an atom and not a list, then CONS can be used. Since NIL is also an atom, this could be a weak point for certain lists. 4. The final possiblity (Not actually tested, T omitted) is the primary recursive call and assumes that both the CAR and CDR of the list will be lists. APPEND joins lists efficiently. |; ;;------- For more on recursion, the posts of Vladimir Nesterovsky on this newsgroup are enlightening. Tony T is the master of apply and mapcar. Didn't mean to leave anybody out. And here's a direct translation with IF's: (defun ravel (l) (if l (if (atom l) (list l) (if (atom (car l)) (cons (car l) (ravel (cdr l))) (append (ravel (car l)) (ravel (cdr l))))))) Nice post Doug; good explanation of your works. I fully agree with cond, in fact, if you go thru any of posts outside of this thread I frequently favor cond over if. Tony and Vlad? Best minds in the field. They've likely forgotten more than I'll ever know. I was pretty close with my "blind" posts, this one actually works: (defun delist ( lst / a x ) (if lst (if (listp lst) (if (setq a (car lst) x (cdr lst)) (if (listp a) (append (delist a) (if (listp x) (delist x) (list x))) (cons a (if (listp x) (delist x) (list x))) ) (if (listp a) (delist a) (list a)) ) (list lst) ) ) ) I can see without benching that your flatten should be it hands down; it's simply doing less processing. However, the number of lines of code is not necessarily indicative of performance nor do algors have identical performance on different data aggregates. But I repeat myself. It is/was fun trying to code alternative code only using listp: it's good to attack problem from different angles; use different functions if for nothing else than to prevent in box mentality. As for a listp only version, I can't visualise a more concise version than above, though that's probably because I'm still sporting that 30+ hour sleep deficit this week (last night no better), so I welcome any version using only listp that is better coded/distilled, particularly if it sports better performance. Thanks again for sharing your time, expertise and enthusiasm. Cheers (Puckett) --
I think a test is in order to see which functions at the fastest rate. I don't know how to do this, never got into the timing thing, but perhaps someone could find out, then we all could adapt to the most efficient version?
