Author Topic: split list into lists  (Read 16210 times)

0 Members and 1 Guest are viewing this topic.

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« on: January 14, 2005, 11:40:10 AM »
I'm having a brain freeze problem today!
I want to parse a list into smaller lists excluding a certain item.  Example, given the list
Code: [Select]
(5 4 3 0 9 8 7 0 6 7 8) separate it into a list of smaller lists such as
Code: [Select]
((543)(987)(678))
I can't for the life of me figure this out! Maybe because it's Friday. :D
TheSwamp.org  (serving the CAD community since 2003)

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #1 on: January 14, 2005, 12:01:41 PM »
Always three items?
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« Reply #2 on: January 14, 2005, 12:05:09 PM »
Quote from: Se7en
Always three items?

Nope!! can be any number.
TheSwamp.org  (serving the CAD community since 2003)

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #3 on: January 14, 2005, 12:26:10 PM »
What?! Your killing me!

...Fine, give me a few more min.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

whdjr

  • Guest
split list into lists
« Reply #4 on: January 14, 2005, 12:35:40 PM »
Are you always going to use 0 as a divider?

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« Reply #5 on: January 14, 2005, 12:36:37 PM »
Quote from: whdjr
Are you always going to use 0 as a divider?

yes, well it's always a constant.
TheSwamp.org  (serving the CAD community since 2003)

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #6 on: January 14, 2005, 12:44:41 PM »
Sorry i dont have more time to test this more. But this is a quick run thru. No pseudo code, no nothing. Just whiped it off the top of my head.  

(second run at it though ...*Ahem!?*)

Code: [Select]
;;; Parse list
;;; Split a list into parts delimited of a specific delim.
;;;
;;; Example:
;;; Command: (setq lst '(1 0 2 0 5 0 5 9 2 3 4 7 8 9 5 0 7 8 9))
;;; (1 0 2 0 5 0 5 9 2 3 4 7 8 9 5 0 7 8 9)
;;;
;;; Command: (parselst 3 0 lst)
;;; ((1 2 5) (5 5 9) (5 9 2) (3 4 7) (8 9 5) (7 8 9))
(defun parselst (nu del alst / pop# isdel nlst)
  (defun isdel (a b) (= a b))
  (defun pop# (alst / cntr nlst)
    (setq cntr 0 nlst '() )
    (while
      (< (length nlst) nu)
      (if (isdel (nth cntr alst) del)
        (setq cntr (1+ cntr)))      
      (setq nlst (cons (nth cntr alst) nlst))
      (setq cntr (1+ cntr))
      )
    (reverse nlst)
    )
  (while (>= (length alst) nu)
    (setq nlst (cons (pop# alst) nlst))
    (setq alst (cdddr alst))
   )
  (reverse nlst)
 )
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #7 on: January 14, 2005, 12:55:19 PM »
Whoa nelly!  Thats wrong!?

Hold on I'll fix it.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

SMadsen

  • Guest
split list into lists
« Reply #8 on: January 14, 2005, 01:24:39 PM »
Mark, it's just a parser with a delimiter you're making, right? e.g.

(func 8 '(5 4 3 0 9 8 9 0 5 6 8 )) -> ((5 4 3 0 9) (9 0 5 6))

Code: [Select]
(defun parselst (item lst / l ll)
  (while lst
    (cond ((not (eq (car lst) item))
           (setq l (cons (car lst) l)))
          ((setq ll (cons (reverse l) ll)
                 l  nil))
    )
    (setq lst (cdr lst))
  )
  (reverse (if l (cons (reverse l) ll) ll))
)

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« Reply #9 on: January 14, 2005, 01:38:56 PM »
Quote from: SMadsen
Mark, it's just a parser with a delimiter you're making, right?

Yes that is correct. That's really close Stig, close enough to get me going anyway. thanks.

Output w/ my list
Code: [Select]

ll = (32 53 54 46 48 48 32 32 55 56 32 32 56 56 32)
(parselst 32 ll)
(nil (53 54 46 48 48) nil (55 56) nil (56 56))
TheSwamp.org  (serving the CAD community since 2003)

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #10 on: January 14, 2005, 02:11:06 PM »
More code:
Code: [Select]
;;-------------------------------------------------
;; Functions originated by Ken Alexander (03-05-03)
;; that are 10X faster than @cv_parse_list, yet limited
;; to only pairs or triplets.
;; Thanks, Ken!
;; (01-02-04) corrected to (while old ...)
;; Revised (01-16-04) to increase speed thanks to Tony T's
;; example of using (while (setq ...))
(defun @cv_double_up (old / new)
  (and
    old
    (while
      (setq new (cons (list (car old) (cadr old)) new)
            old (cddr old)
      )
    )
  )
  (reverse new)
)
;; Revised (01-16-04) to increase speed thanks to Tony T's
;; example of using (while (setq ...))
(defun @cv_triple_up (old / new)
  (and
    old
    (while
      (setq new (cons (list (car old) (cadr old) (caddr old)) new)
            old (cdddr old)
      )
    )
  )
  (reverse new)
)
;; (01-16-04) combination of @cv_double_up and @cv_triple_up
;; Not yet employed.
(defun @cv_grouplist (old n / new)
  ;; n must be 2 or 3
  (and
    old
    (cond
      ((= n 2)
       (while
         (setq new (cons (list (car old) (cadr old)) new)
               old (cddr old)
         )
       )
      )
      ((= n 3)
       (while
         (setq new (cons (list (car old) (cadr old) (caddr old)) new)
               old (cdddr old)
         )
       )
      )
    )
  )
  (reverse new)
)
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

SMadsen

  • Guest
split list into lists
« Reply #11 on: January 14, 2005, 02:23:25 PM »
Quote from: Mark Thomas
Yes that is correct. That's really close Stig, close enough to get me going anyway. thanks.

Oh well, one typo more or less .. :)  It could've been avoided by using APPEND instead (and code made shorter) but I like CONS better

Code: [Select]
(defun parselst (item lst / l ll)
  (while lst
    (cond ((not (eq (car lst) item))
           (setq l (cons (car lst) l)))
          ((setq ll (if l (cons (reverse l) ll) ll)
                 l  nil))
    )
    (setq lst (cdr lst))
  )
  (reverse (if l (cons (reverse l) ll) ll))
)

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #12 on: January 14, 2005, 03:14:26 PM »
Ooops, Guess I wasn't paying attention. :oops:
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« Reply #13 on: January 14, 2005, 03:37:05 PM »
Thanks Stig that's works like a champ. I was trying to wrap the whole thing into a 'apply append mapcar' type setup.
TheSwamp.org  (serving the CAD community since 2003)

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #14 on: January 14, 2005, 04:12:51 PM »
Ok, im sorry. I got hung up here at work.  ...but im glad you got it working.

BTW, Thats all you wanted?! What was the 'list of three' thing?  (Im not sorry anymore.)
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

SMadsen

  • Guest
split list into lists
« Reply #15 on: January 14, 2005, 06:01:45 PM »
Well .. John .. that's ok but anyone making it a recursive can buy me a ticket to Orlando next year :)

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #16 on: January 14, 2005, 06:35:45 PM »
I did have this one for strings:
Code: [Select]
;--subroutine to take text with char (ex.~) & create list
(defun gettextlist (str_text char / char_len kks kkk kkl)
  (setq list_text nil)
  (setq char_len (strlen char))
  (setq kks 1
kkk 1
kkl (strlen str_text)
  )
  (while (<= kkk kkl)
    (if (= (substr str_text kkk char_len) char)
      (progn
(setq
 list_text (append list_text
   (list (substr str_text kks (- kkk kks)))
   )
)
(setq kks (+ kkk char_len))
      )
    )
    (setq kkk (1+ kkk))
  )
  (setq list_text (append list_text (list (substr str_text kks))))
)
 ;Call be (GETTEXTLIST "This is a Test String" " ")
 ;returns ("This" "is" "a" "Test" "String")
 ;Note that the CHAR can be more than 1 character long - example -
 ;(GETTEXTLIST "A12B12C" "12") returns ("A" "B" "C")
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #17 on: January 14, 2005, 09:36:09 PM »
Quote from: SMadsen
Well .. John .. that's ok but anyone making it a recursive can buy me a ticket to Orlando next year :)

Can't afford a ticket to Orlando :shock:
Code: [Select]
 (defun parselst (item lst / ll)
    (while lst
      (if (eq (car lst) item)
        (setq ll  (if ll
                    (cons (reverse ll) (parselst item (cdr lst)))
                    (parselst item (cdr lst)))
              lst nil
        )
        (setq ll  (cons (car lst) ll)
              lst (cdr lst)
        )
      )
    )
   ll
 )
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #18 on: January 14, 2005, 10:01:45 PM »
Quote from: SMadsen
Well .. John .. that's ok but anyone making it a recursive can buy me a ticket to Orlando next year :)


Humm.

Although i would really (read: R E A L L Y) like to beat you Stig. ...I cant without cheating. (I mean it would be easy with a seperate varable or a "container" argument to the main procedure, but other then those options i just cant think of any way to make it a recursive procedure. --BUT that didnt stop me from trying. :lol: )

:P
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #19 on: January 14, 2005, 10:02:52 PM »
...Hold on i just saw CABs post. Im goona check this out!
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #20 on: January 14, 2005, 10:12:46 PM »
Ingenious!!!!  

How in dahell did you do that?!  ...:shock: :(

....humm
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #21 on: January 14, 2005, 10:23:24 PM »
CAB your not suposed to be ...damn man!?

Comment that code meh man!

*Se7en turns away and grumbes about recursive process' in recursive procedures.*
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« Reply #22 on: January 14, 2005, 10:27:19 PM »
Put that in english man .............
TheSwamp.org  (serving the CAD community since 2003)

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #23 on: January 14, 2005, 11:09:04 PM »
Here is my FOREACH version.
Code: [Select]
 (defun parselst (item lst / ll l)
    (foreach x lst
      (cond ((and l (eq x item))
              (setq ll (cons (reverse l) ll) l nil))
            ((eq x item))
            ((setq l (cons x l)))
      )
    )
    (reverse ll)
  )


 Se7en's got me confused :)
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

MP

  • Seagull
  • Posts: 17750
  • Have thousands of dwgs to process? Contact me.
split list into lists
« Reply #24 on: January 14, 2005, 11:21:41 PM »
If the idea is to parse a list into sublists based on an item as a trigger (and to be excluded from the results) here's a quick stab ...
Code: [Select]
(defun ParseOnX ( lst x / sublst result )
    (foreach i (reverse lst)
        (if (eq i x)
            (setq
                result (cons sublst result)
                sublst nil                
            )
            (setq sublst (cons i sublst))
        )    
    )
    (vl-remove-if 'null
        (if sublst
            (cons sublst result)
            result
        )    
    )    
)

;;  some data

(setq lst
   '(
        0 1 2 3 4
        0 1 2 3 4
        0 1 2 3 4
        0 1 2 3 4
    )
)

;;  examples ...

(ParseOnX lst 0) >> ((1 2 3 4) (1 2 3 4) (1 2 3 4) (1 2 3 4))

(ParseOnX lst 1) >> ((0) (2 3 4 0) (2 3 4 0) (2 3 4 0) (2 3 4))

(ParseOnX lst 2) >> ((0 1) (3 4 0 1) (3 4 0 1) (3 4 0 1) (3 4))

(ParseOnX lst 3) >> ((0 1 2) (4 0 1 2) (4 0 1 2) (4 0 1 2) (4))

(ParseOnX lst 4) >> ((0 1 2 3) (0 1 2 3) (0 1 2 3) (0 1 2 3))

Is that watcha had in mind?
Engineering Technologist • CAD Automation Practitioner
Automation ▸ Design ▸ Drafting ▸ Document Control ▸ Client
cadanalyst@gmail.comhttp://cadanalyst.slack.comhttp://linkedin.com/in/cadanalyst

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« Reply #25 on: January 15, 2005, 12:18:48 AM »
Quote from: MP
Is that watcha had in mind?

exactly!!

thanks for all the posts guys. I've enjoyed them. :D
TheSwamp.org  (serving the CAD community since 2003)

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #26 on: January 15, 2005, 11:05:04 AM »
lol. CAB that was awesome.

Your procedure is a recursive procedure correct? Well...

(cons (reverse ll) (parselst item (cdr lst)))
;; This is a recursive process (Inside a recursive procedure)

This is both good and bad. This method is bad because it chews up the stack F A S T! (So a fairly moderate size list could overrun your stack.) and its good because its cool as hell! (Its a neat trick used to solve problems like this. ...It kinda gives you a second pair of hands when operating on items.)

Although your procedure is cool/fun/nice to look at/study I wouldnt suggest using it in any major app. Iteration is, and always will be, faster/better when large amounts of data could be used.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #27 on: January 15, 2005, 11:11:28 AM »
Thanks for the heads up, as you know I'm not a recursive kinda guy.
I though any routine that called itself was a recursive procedure.

Can you tel me how nush data has to be fed this routine to overrun the stack?
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #28 on: January 15, 2005, 11:33:49 AM »
No problem.

heh, no. Im not that smart. (Theres a formula but i dont understand it. :D )

There are two types of Recursive procedures.  (well theres more but for the sake of this convo...)
1. A recursive procedure using an iterative process.

2.  A recursive procedure using a recursive (actualy called: linear recursive) process.

You used both in your procedure.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #29 on: January 15, 2005, 11:43:31 AM »
Well you have me confused about this statement.
;; This is a recursive process (Inside a recursive procedure)

This is how the routine works:
With this list (32 53 54 46 48 48 32 32 55 56 32 32 56 56 32)
Code: [Select]
(if (eq (car lst) item) ----  true (32)
(if ll (cons (reverse ll) (parselst item (cdr lst)))
        (parselst item (cdr lst)))
          ll is false so sent the remainder of the list through
          (53 54 46 48 48 32 32 55 56 32 32 56 56 32)
 next loop
   (if (eq (car lst) item) ----  false(53)
   so execute the while loop
   (setq ll  (cons (car lst) ll)
         lst (cdr lst)
which builds (53 54 46 48 48)
at the next 32 send this through (32 55 56 32 32 56 56 32)
because its 32 again send this through (55 56 32 32 56 56 32)
collect this (55 56)
send this through (56 56 32)


Well you get the idea

It may at first glance look like the while loop would send the data through
multiple times but because of the setq lst nil the loop is stopped and only
one pass is done.

So it look like a normal recursive to me, but I am inexperienced at this procedure
and may be missing something.
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #30 on: January 15, 2005, 11:55:04 AM »
Basicly that statment means that there is still stuff to do to the stuff after the stuff has gone thru the procedure again.  ...awe crap that sounds even more confusing.  (hold on a sec.)

Read this and let me know if it helps any: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #31 on: January 15, 2005, 03:50:15 PM »
Ugh, I'll get back to you :)  after i read that.
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #32 on: January 15, 2005, 09:34:33 PM »
Running this test routine see the results below.
Code: [Select]
(defun c:test (/ lst1 level)
  (defun parselst (item lst / ll)
    (print (setq level (1+ level)))
    (while lst
      (if (eq (car lst) item)
        (setq ll  (if ll
                    (cons (reverse ll) (parselst item (cdr lst)))
                    (parselst item (cdr lst))
                  )
              lst nil
        )
        (setq ll  (cons (car lst) ll)
              lst (cdr lst)
        )
      )
    )
    (print ll)
    ll
  )

  (setq lst1 (list 32 53 54 46 48 48 32 32 55 56 32 32 56 56 32))
  (setq level 0)
  (print)
  (parselst 32 lst1)
  (princ)
)

Code: [Select]
Command: test


1
2
3
4
5
6
7
nil
((56 56))
((56 56))
((55 56) (56 56))
((55 56) (56 56))
((53 54 46 48 48) (55 56) (56 56))
((53 54 46 48 48) (55 56) (56 56))

Command:


You see the recursion is leaner. Right?
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #33 on: January 16, 2005, 09:05:59 PM »
No. (At least i dont think so.)

In my spare time tomorrow im gonna wrap my head around your code a bit and try to understand it better.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #34 on: January 16, 2005, 11:13:50 PM »
Ok, here is the code commented.
 
Code: [Select]
(defun parselst (item lst / ll)
    (print (setq level (1+ level))); debug
    (while lst  ; loop until lst is nil
      (if (eq (car lst) item) ; test if match with item in this case 32
        ;;  yes a match
        (setq ll  (if ll ; yes items were added to ll before getting to 32
                    ;; so combine the items in ll with items returned by parselst
                    (cons (reverse ll) (parselst item (cdr lst)))
                    ;; no items in ll because we got another 32 so
                    (parselst item (cdr lst)) ; don't combine, just return items returned by parselst
                  )
              lst nil ; null lst so loop will stop
        ) ; end setq
        ;;  No not a match so
        (setq ll  (cons (car lst) ll) ; add items to ll until the next 32 or end of list
              lst (cdr lst) ; remove the first item from the list
        ) ; end setq
      ) ; endif
    ) ; end while
    (print ll); debug
    ll ; return collected items in ll
  )

 
 Psudo code:
 Loop items in list
 If not 32 then add items to ll
 If 32 then send list with the first item removed back through the routine.
 combine the returned list with ll only if there are items in ll
 The fact that you need to reverse ll means you need an if statement
 
Code: [Select]
(if ll (cons (reverse ll) (parselst item (cdr lst)))
          (parselst item (cdr lst))
  )

 
 There may be a way to eliminate this IF statement but I couldn't find it.
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #35 on: January 17, 2005, 01:31:15 PM »
CAB, Im sorry to have to say this to you, but it appears that you have a Tree recusion procedure. Meaning that your data (each peice of information) is filtered thru a series of conditions/process and built into a final result. This is a very complex recursion concept usualy used in encoding. (Congratulations! :P )  I drew a picture of whats going on: (I hope it turns out in this post ...Nope, it looks like crap. So cut and paste this into notepad or a text editor to see it.)
Code: [Select]

 @@@@@  ;; Procedure start
 ( ~ )  ;; Loop
  ??    ;; Conditional
  /\    ;; ...
 Y  N   ;; Enter switch
 |  |   ;; YES Switch - Enter another contitional
??  |   ;; NO Switch  - Enter normal process
/\  |   ;;
Y N |   ;; YES Switch (YS) - Enter switch
| | |   ;;
X | |   ;; (YS) YES Switch - Process based on recursion
@ @ |   ;; (YS) NO Switch  - Recurse
    |   ;;
    X   ;; NO Switch - Continue loop/proceses
  (/~/) ;; End loop
    =   ;; Return result


No but seriously, your procedure is amazing. You should be happy. However just so you know that the method you are using in this takes is extreamly in-efficient. (It gobbles up stack memory like there's no tomorow.)

But anyways i hope my lil picture halped out a bit. If not, just forget it and know that im sorry.  :D
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #36 on: January 17, 2005, 02:11:46 PM »
John,
Nice picture..

I think you have missunderstood the [Yes No] portion of my code.
It actually has nothing to do with the recrusion.
Here is what I am talking about.
Code: [Select]

(if ll
   (cons (reverse ll) (parselst item (cdr lst)))
                      (parselst item (cdr lst))
  )

It appears as if there is a branch but there is not as both calls to parselst are identical.
If ll is not nil the statement combines ll with the result of parselst
else ll is nil and the statement returns parselst only
So you see parselst is the same, there is no branch
Let me see if a can write the code another way to show the result.
OK here it is, you see there is no branch
Code: [Select]
 (defun parselst (item lst / ll tmp)
    (while lst
      (if (eq (car lst) item)
        (setq tmp (parselst item (cdr lst))
              ll  (if ll (cons (reverse ll) tmp) tmp)
              lst nil
        )
        (setq ll  (cons (car lst) ll)
              lst (cdr lst)
        )
      )
    )
   ll
 )
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #37 on: January 17, 2005, 02:19:18 PM »
*Phew!*  ...Im confused. (I mean my head is smokin'!)
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #38 on: January 17, 2005, 02:28:56 PM »
LOL  I'm glad I'm not the only one.. :D
Here is my conclusion,
 Because the routine will only call itself once and then return I think it is leaner.
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #39 on: January 17, 2005, 02:30:44 PM »
By the way, where did Stig go? He started this. 8)
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

SMadsen

  • Guest
split list into lists
« Reply #40 on: January 17, 2005, 06:04:39 PM »
Quote from: CAB
By the way, where did Stig go? He started this. 8)

Nah .. Mark started it, remember? :)
Nice work, CAB.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #41 on: January 17, 2005, 06:42:01 PM »
Quote from: SMadsen
Well .. John .. that's ok but anyone making it a recursive can buy me a ticket to Orlando next year :)

I was refering to starting this. :)

Thanks Stig.
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

SMadsen

  • Guest
split list into lists
« Reply #42 on: January 18, 2005, 06:14:10 PM »
Quote from: Se7en
Read this and let me know if it helps any: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

Another good source for recursion is McCarthy's 1960 (!) publication "Recursive Functions of Symbolic Expressions and Their Computation by Machine". Link to PDF can be found here.

JohnK

  • Administrator
  • Seagull
  • Posts: 10603
split list into lists
« Reply #43 on: January 18, 2005, 09:00:11 PM »
Ohh...Dont read that to fast. (Man i have to read those paragraphs at least twice in order to catch all of it. :D)

Good find Stig!
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

SMadsen

  • Guest
split list into lists
« Reply #44 on: January 19, 2005, 04:59:04 AM »
Oh you can catch all of it? That must be cool :)

It does use some weird syntax but it's essentially the same techniques today.
Here's an effort of "translating" some of the syntax (written last night so any errors are probably due to lack of sleep):

Code: [Select]
;;; From: Recursive Functions of Symbolic Expressions
;;;       and Their Computation by Machine, Part I
;;;       John McCarthy, MIT, Cambridge, Mass.
;;;       April 1960

;;; GCD
;;; Greatest common denominator of two integers m and n
(defun mcGCD (m n)
  (cond ((> m n) (mcGCD n m))
        ((zerop (rem n m)) m)
        ((mcGCD (rem n m) m))
  )
)

;;; SQRT
;;; Newtons approximation algorithm for finding square root
;;; of a number a where x is initial approximation and e is a
;;; value that satisfies |y^2 - a| < e for y being an acceptable
;;; approximation (approximation factor).
;;; E.g.:
;;  (mcsqrt 25.0 5.4 5)     -> 5.4
;;  (mcsqrt 25.0 5.4 0.001) -> 5.0002
(defun mcSqrt (a x e)
  (cond ((or (minusp x)(zerop x)) nil)
        ((< (abs (- (* x x) a)) e) x)
        ((mcSqrt a (* 0.5 (+ x (/ a x))) e))
  )
)

;;; NULL
;;; Not recursive but a definition of the function NULL
;;; (the empty list '() is also defined as the atomic
;;; symbol nil)
(defun mcNull (x)
  (and (atom x) (eq x nil))
)

;;; SUBST
;;; Substitute all occurences of y in z with x.
(defun mcSubst (x y z)
  (cond ((atom z)(if (eq z y) x z))
        ((cons (car z)(subst x y (cdr z))))
  )
)

;;; EQUAL
;;; Returns T if x and y are identical atoms or expressions.
;;; Note: There's no fuzz factor in this definition
(defun mcEqual (x y)
  (or (and (atom x)(atom y)(eq x y))
      (and (not (atom x))(not (atom y))
           (equal (car x)(car y))
           (equal (cdr x)(cdr y))
      )
  )
)

;;; PAIR
;;; Pairs corresponding elements of x and y
;;; Note: No equivalent func in AutoLISP
;;; E.g.
;;  (pair '(1 2)'(3 4)) -> ((1 3) (2 4))
;;  (pair '(1 2 (3 4)) '(3 4 (5 6))) ->
;;    ((1 3) (2 4) ((3 4) (5 6)))
(defun pair (x y)
  (cond ((and (null x)(null y)) nil)
        ((and (not (atom x))(not (atom y)))
         (cons (list (car x)(car y))
               (pair (cdr x)(cdr y)))
        )
  )
)

;;; APPEND
;;; Appends list x to list y
;;; Note: Doesn't check if neither arguments are lists.
;;;       If y is an atom, it is appended as CDR element
;;;       within an improper list.
;;; E.g.
;;  (mcAppend '(1 2) '(3 4)) -> (1 2 3 4)
;;  (mcAppend '(1 2) 'a)     -> (1 2 . A) !!
(defun mcAppend (x y)
  (cond ((null x) y)
        ((cons (car x)(mcAppend (cdr x) y)))
  )
)

;;; AMONG
;;; Returns T if x occurs among the elements of list y.
;;; Note: This function differs from MEMBER by being a
;;;       predicate function (returning T or nil)
(defun among (x y)
  (and (not (null y))
       (or (equal x (car y))
           (among x (cdr y))
       )
  )
)

;;; ASSOC
;;; Returns item in association list y where x is the
;;; CAR item.
;;; E.g.
;;  (mcAssoc 3 '((1 2)(2 3)(3 4)(4 5))) -> (3 4)
;;  (mcAssoc 5 '((1 2)(2 3)(3 4)(4 5))) -> nil
(defun mcAssoc (x y)
  (cond ((eq (caar y) x)(cadar y))
        ((assoc x (cdr y)))
  )
)

;;; SUBLIS
;;; "Here x is assumed to have the form of a list of pairs
;;; ((u1 v1) ... (un vn)), where the u's are atomic,
;;; and y may be any S-expression.
;;; The value of sublis[x y] is the result of substituting
;;; each v for the corresponding u in y. In order to define
;;; sublis, we first define an auxiliary function."
;;; E.g.
;;  (setq alst '((1 2)(3 4)(5 6)))
;;  (sublis alst 3) -> 4
;;  (sublis alst '(3 5)) -> (4 6)
;;  (sublis alst '(3 4)) -> (4 4)
;;  (sublis alst '(1 (3 . 4)))   -> (2 (4 . 4))
;;  (sublis alst '(1 (3 5 . 4))) -> (2 (4 6 . 4))
(defun sublis (x y)
  (defun sub2 (x z)
    (cond ((null x) z)
          ((eq (caar x) z)(cadar x))
          ((sub2 (cdr x) z))
    )
  )
  (cond ((atom y)(sub2 x y))
        ((cons (sublis x (car y))(sublis x (cdr y))))
  )
)

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
split list into lists
« Reply #45 on: January 19, 2005, 08:02:59 AM »
Well I need a recursion for dummy's version of that paper.

Stig you're a wild man.. :shock:
Looks like you got a handle on it. :)
I've reached the age where the happy hour is a nap. (°¿°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

Mark

  • Custom Title
  • Seagull
  • Posts: 28753
split list into lists
« Reply #46 on: January 19, 2005, 08:15:24 AM »
Quote
Another good source for recursion is McCarthy's 1960 (!) publication "Recursive Functions of Symbolic Expressions ............


that's good stuff Mr. Madsen, thanks.
TheSwamp.org  (serving the CAD community since 2003)

SMadsen

  • Guest
split list into lists
« Reply #47 on: January 19, 2005, 08:18:07 AM »
Nah it's just pure transcript, CAB.

Forgot to add this line in the SUBLIS examples:
(setq alst '((1 2)(3 4)(5 6)))