Topic: Bicursion ...

[MP]

It wasn't supposed to. Only supposed to explain why Mark's routine can't handle multiple atoms on same level. That's why Doug's routine had to implement multiple conditions.

Ackkk: Too little sleep, too much coffee. Sorry?

Nevermind it can only handle one kind of list though, did you try to benchmark it? It's pretty fast  

[CAB]

Well I finally got mine to work.
It aint pretty but.

Code: [Select]

(defun delist (lst / 1-list a)
  (while lst
    (if (listp lst)
      (if (and (listp (setq a (car lst))) a)
        (setq 1-list (append (delist a) 1-list))
        (setq 1-list (cons a 1-list))
      )
      (setq 1-list (cons lst 1-list))
    )
    (setq lst (cond ((listp lst)(cdr lst))))
  )
  1-list
)


Flattened length = 8
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (DELIST LST)......1272 / 2.21 <fastest>
    (SQUISH LST)......1662 / 1.69
    (FLATTEN LST).....2814 / 1.00 <slowest>

Flattened length = 16
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (DELIST LST)......1792 / 1.40 <fastest>
    (FLATTEN LST).....1893 / 1.33
    (SQUISH LST)......2513 / 1.00 <slowest>

Flattened length = 32
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):

    (DELIST LST)......1482 / 1.42 <fastest>
    (FLATTEN LST).....1563 / 1.35
    (SQUISH LST)......2103 / 1.00 <slowest>

Flattened length = 64
Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):

    (DELIST LST)......1392 / 1.40 <fastest>
    (FLATTEN LST).....1502 / 1.29
    (SQUISH LST)......1942 / 1.00 <slowest>

Flattened length = 128
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (DELIST LST)......1502 / 1.25 <fastest>
    (FLATTEN LST).....1582 / 1.18
    (SQUISH LST)......1873 / 1.00 <slowest>

Flattened length = 256
Benchmarking ............Elapsed milliseconds / relative speed for 512 iteration(s):

    (DELIST LST)......1772 / 1.05 <fastest>
    (SQUISH LST)......1853 / 1.01
    (FLATTEN LST).....1863 / 1.00 <slowest>

Flattened length = 512
Benchmarking ...........Elapsed milliseconds / relative speed for 256 iteration(s):

    (SQUISH LST)......1833 / 1.33 <fastest>    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    (DELIST LST)......2354 / 1.03
    (FLATTEN LST).....2433 / 1.00 <slowest>

Flattened length = 1024
Benchmarking ..........Elapsed milliseconds / relative speed for 128 iteration(s):

    (SQUISH LST)......1833 / 1.99 <fastest>
    (DELIST LST)......3535 / 1.03
    (FLATTEN LST).....3645 / 1.00 <slowest>

Flattened length = 2048
Benchmarking .........Elapsed milliseconds / relative speed for 64 iteration(s):

    (SQUISH LST)......1833 / 3.29 <fastest>
    (DELIST LST)......5898 / 1.02
    (FLATTEN LST).....6039 / 1.00 <slowest>

[CAB]

MP,
What happens when you use this list for your test?

Code: [Select]

(setq lst '((1 . 2) (1 nil 3) ((11 12) (21 22) 4)))

[whdjr]

 

KABOOM!

   

[MP]

Hi Charles,

It is not intended for dotted pairs. From my initial post:

Many years ago I had competed in a contest to write a function to flatten a nested list (no dotted pairs) to a non nested list.

But thank you for the heads up; greatly appreciated.

:D

[CAB]

Hi Charles,

It is not intended for dotted pairs. From my initial post:

Many years ago I had competed in a contest to write a function to flatten a nested list (no dotted pairs) to a non nested list.

But thank you for the heads up; greatly appreciated.

MP,
You're quite right, I'm sure I read that yesterday but that was yesterday.
Sorry about that.

[MP]

No worries Charles, it's all propellers here!

[MP]

Hey Charles, did you view the results from your DeList? Hint, hint. :)

[CAB]

Hey Charles, did you view the results from your DeList? Hint, hint.

Are you talking about the fact the return list is reversed?
I had to modify the code as follows to fix that.
Do you have a better solution?

Code: [Select]

(setq lst1 '((1 . 2) (1 nil 3) ((11 12) (21 22) 4)))
(setq lst2 '(1 (2 (3 (4 (5 (nil (7 (8)))))))))
(setq lst3 '((((((((1) 2) 3) 4) 5) 6) 7) 8))

(defun delist (lst / delst)
  (defun delst (lst / 1-list a)
    (while lst
      (if (and (listp lst) (listp (setq a (car lst))) a)
        (setq 1-list (append (delst a) 1-list))
        (setq 1-list (cons (cond ((listp lst) a)(lst))1-list))
      )
      (setq lst (cond ((listp lst) (cdr lst))))
    )
    1-list
  )
  (reverse (delst lst))
)

(princ (delist lst1))
(print)
(princ (delist lst2))
(print)
(princ (delist lst3))

Result

(1 2 1 nil 3 11 12 21 22 4)
(1 2 3 4 5 nil 7 8)
(1 2 3 4 5 6 7 8)


And the fix killed my advantage.

Code: [Select]

Flattened length = 8
Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (DELIST LST)......1532 / 1.23 <fastest>
    (FLATTEN LST).....1533 / 1.23
    (SQUISH LST)......1882 / 1.00 <slowest>

Flattened length = 16
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):

    (DELIST LST)......1001 / 1.31 <fastest>
    (FLATTEN LST).....1021 / 1.28
    (SQUISH LST)......1311 / 1.00 <slowest>

Flattened length = 32
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):

    (FLATTEN LST).....1753 / 1.30 <fastest>
    (DELIST LST)......1783 / 1.28
    (SQUISH LST)......2283 / 1.00 <slowest>

Flattened length = 64
Benchmarking ..............Elapsed milliseconds / relative speed for 2048 iteration(s):

    (DELIST LST)......1752 / 1.24 <fastest>
    (FLATTEN LST).....1772 / 1.23
    (SQUISH LST)......2174 / 1.00 <slowest>

Flattened length = 128
Benchmarking .............Elapsed milliseconds / relative speed for 1024 iteration(s):

    (FLATTEN LST).....1963 / 1.06 <fastest>
    (DELIST LST)......1983 / 1.05
    (SQUISH LST)......2083 / 1.00 <slowest>

Flattened length = 256
Benchmarking ...........Elapsed milliseconds / relative speed for 256 iteration(s):

    (SQUISH LST)......1002 / 1.20 <fastest>
    (FLATTEN LST).....1191 / 1.01
    (DELIST LST)......1202 / 1.00 <slowest>

PS Cool propellers

[MP]

Hi Charles --

I'm not seeing the rationale for the nested defun delst (which is not local incidentally). It's performing the same thing the body of delist could. I'd just reverse 1-list when you're done.

Note, it's tempting to think, hmmm, the raw list has fewer members than the processed list, it should take less time to reverse.

However, it will yeild wonky results:

Code: [Select]

(reverse '(1(2(3(4(5(6(7(8)))))))))

=> ((2 (3 (4 (5 (6 (7 (8))))))) 1)

Flattening that would produce:

=> (2 3 4 5 6 7 8 1)

Reversing:

=> (1 8 7 6 5 4 3 2)
Not quite right!

:D

[CAB]

You're confunen me. Easy to do I know.

I edited my previous post.
> localized the function
> added the raw list to compare with the results.

The delist call to delst just reverses the return value from delst.
It does not send a reversed raw list. As you say that would produce incorrect results.

[MP]

Sorry Charles, was getting ready for work when I hastilly made that post. The point I was trying to make is this ...

Code: [Select]

(defun foo1 ( lst / result )
    (foreach x lst
        (if SomeConditionMet
            (setq result
                (cons x result)
            )
        )    
    )
    (reverse result)
)

(defun foo2 ( lst / result )
    (foreach x (reverse lst)
        (if SomeConditionMet
            (setq result
                (cons x result)
            )
        )    
    )
    result
)
In foo1 the order of the elements in variable result is reversed from the original, hense you have to reverse its contents when returning it to the caller.

In foo2 the order of the elements in variable result is the same as the original, hense no need to reverse it when returning it to the caller.

Speaking generally, When dealing with flat lists (the norm), foo1 is preferable when the result has fewer elements than the original (the norm); foo2 prefereable when the result has more elements than the original.

However, reversing a nested list, processing it and then returning the result may not yield the desired result! </point>

But I'm not saying that's what you did, recall "Note, it's tempting to think ..."

Cheers.

[Kerry]

A traffic cop here .. .
pointed me to this thread.

Way cool.

[uncoolperson]

cheater way to flatten a list.... :ugly:

Code: [Select]

(defun buldge (alist)
  (setq alist (vl-princ-to-string alist))
(while (vl-string-search "(" (setq alist (vl-string-subst "" "(" alist))))
(while (vl-string-search ")" (setq alist (vl-string-subst "" ")" alist))))
(read (strcat "(" alist ")"))
  )

[Kerry]

Try that on this  !!
(setq lst2 '(1 (2 (3 (4 (5 "ABC" "DE FG"(nil (7 (8 )))))))))

Then back to the drawing board ..