Topic: List in Lists--(alanjt)

[Jeff H]

If someone has a second can they explain the logic here

From this Link
OP wanted
((1 2 3) (2 3 4) ((5 7 3)) (((G))) ((((A)))))
to list
(1 2 3 2 3 4 5 7 3 G A)

alanjt posted this code

Code: [Select]

(defun AT:ListCondense (lst)
  ;; Condense list of sublists to a single list
  ;; lst - list of lists to process
  ;; Alan J. Thompson, 08.10.10
  (if lst
    (if (listp lst)
      (append (AT:ListCondense (car lst)) (AT:ListCondense (cdr lst)))
      (list lst)
    )
  )
)


[Lee Mac]

lol, I have the test in reverse.

The logic would be something like the following:

Code: [Select]

(defun AT:ListCondense ( lst )
 
[color=green]  ;; Condense list of sublists to a single list
  ;; lst - list of lists to process
  ;; Alan J. Thompson, 08.10.10[/color]

  (if lst

[color=green]    ;; If we have data to work with...[/color]
   
    (if (listp lst)

[color=green]      ;; If such data is a List (consider that (listp nil)=T, but we have already
      ;; tested for nil, so we won't enter a recursive black hole...[/color]
     
      (append

[color=green]        ;; Then Append the result of processing the first item...
        ;; [ If the first item is a list, it will be recursively processed again, else
        ;;   see below for 'else' condition ][/color]
       
        (AT:ListCondense (car lst))

[color=green]        ;; ...With the result of processing the rest of the list
        ;; [ If we have a dotted pair, (cdr lst) will return an atom, hence
        ;;   we skip again to the 'else' condition, otherwise we will just
        ;;   iterate through each item of the list, until nil. ][/color]
       
        (AT:ListCondense (cdr lst))
      )
[color=green]
      ;; Else we don't have a list, so list the item, so that
      ;; the function returns a list to be either appended or returned.[/color]
     
      (list lst)
    )
  )
)
[ I hope I'm not stepping on your toes Alan ]

[VovKa]

be careful guys

Code: [Select]

(AT:ListCondense '((1 2) (3 nil 4)))
(LM:Flatten '((1 2) (3 nil 4)))


[gile]

Hi,

A way to understand how recursive functions work is to use the 'trace' LISP function and the vlide 'Trace' window.

Try:

Code: [Select]

(trace AT:ListCondense)
Then run:

Code: [Select]

(AT:ListCondense '((1 2) (3 (4 5))))
In the vlide 'Trace' window you can see all recursive calls and their results:

Code: [Select]

Saisie (AT:LISTCONDENSE ((1 2) (3 (4 5))))
  Saisie (AT:LISTCONDENSE (1 2))
    Saisie (AT:LISTCONDENSE 1)
    Résultat:  (1)
    Saisie (AT:LISTCONDENSE (2))
      Saisie (AT:LISTCONDENSE 2)
      Résultat:  (2)
      Saisie (AT:LISTCONDENSE nil)
      Résultat:  nil
    Résultat:  (2)
  Résultat:  (1 2)
  Saisie (AT:LISTCONDENSE ((3 (4 5))))
    Saisie (AT:LISTCONDENSE (3 (4 5)))
      Saisie (AT:LISTCONDENSE 3)
      Résultat:  (3)
      Saisie (AT:LISTCONDENSE ((4 5)))
        Saisie (AT:LISTCONDENSE (4 5))
          Saisie (AT:LISTCONDENSE 4)
          Résultat:  (4)
          Saisie (AT:LISTCONDENSE (5))
            Saisie (AT:LISTCONDENSE 5)
            Résultat:  (5)
            Saisie (AT:LISTCONDENSE nil)
            Résultat:  nil
          Résultat:  (5)
        Résultat:  (4 5)
        Saisie (AT:LISTCONDENSE nil)
        Résultat:  nil
      Résultat:  (4 5)
    Résultat:  (3 4 5)
    Saisie (AT:LISTCONDENSE nil)
    Résultat:  nil
  Résultat:  (3 4 5)
Résultat:  (1 2 3 4 5)

Here's another way for the same task.
The code isn't so concise but may run a little faster because of less recursive calls and the use of 'cons' instead of 'append' (which is more expansive).

The main function: gc:flatlist uses an auxiliary recursive function: foo.
foo is 'tail recursive' (AFAIK AutoLISP do not optimize tail recursion, but many othe functional languages as F# do) and uses an accumilator (acc) to store the result (in reverse order due to the use of cons).

foo requires two arguments: the list to be processed (lst) and the the list to be returned (acc).
The fuction first evaluates if lst is not nil (empty list)
- if so, calls foo passing it the list tail (cdr) as first argument and, for the second argument, evaluates if the list head (car) is an atom or a list.
-- if it's an atom, just had it to the top of the current accumulator
-- if it's a list, calls foo passing it this list and the current accumulator
- if the list is empty, returns the accumultator

gc:flatlist calls foo passing it the list to process and an empty list as accumulator and reverses the returned list.

Code: [Select]

(defun gc:flatlist (lst / foo)
  (defun foo (lst acc)
    (if lst
      (foo
(cdr lst)
(if (atom (car lst))
  (cons (car lst) acc)
  (foo (car lst) acc)
)
      )
      acc
    )
  )
  (reverse (foo lst nil))
)
Tracing the 'foo' subfunction with the same list as upper:

Code: [Select]

Saisie (FOO ((1 2) (3 (4 5))) nil)
  Saisie (FOO (1 2) nil)
    Saisie (FOO (2) (1))
      Saisie (FOO nil (2 1))
      Résultat:  (2 1)
    Résultat:  (2 1)
  Résultat:  (2 1)
  Saisie (FOO ((3 (4 5))) (2 1))
    Saisie (FOO (3 (4 5)) (2 1))
      Saisie (FOO ((4 5)) (3 2 1))
        Saisie (FOO (4 5) (3 2 1))
          Saisie (FOO (5) (4 3 2 1))
            Saisie (FOO nil (5 4 3 2 1))
            Résultat:  (5 4 3 2 1)
          Résultat:  (5 4 3 2 1)
        Résultat:  (5 4 3 2 1)
        Saisie (FOO nil (5 4 3 2 1))
        Résultat:  (5 4 3 2 1)
      Résultat:  (5 4 3 2 1)
    Résultat:  (5 4 3 2 1)
    Saisie (FOO nil (5 4 3 2 1))
    Résultat:  (5 4 3 2 1)
  Résultat:  (5 4 3 2 1)
Résultat:  (5 4 3 2 1)

[Lee Mac]

be careful guys

Code: [Select]

(AT:ListCondense '((1 2) (3 nil 4)))
(LM:Flatten '((1 2) (3 nil 4)))


One could argue it returns the correct result since nil = empty list, i.e.:

Code: [Select]

(LM:Flatten '((1 2) (3 nil 4)))  ==  (LM:Flatten '((1 2) (3 ( ) 4)))  ==  '(1 2 3 4)
 

[VovKa]

One could argue it returns the correct result since nil = empty list, i.e.:

one could argue that nil = empty atom i.e.:

Code: [Select]

(atom nil)

[gile]

As is, the code I posted consider nil as an atom.
To consider nil as an empty list (and remove it from the result), just replace:
(if (atom (car lst)) ...)
with:
(if (and (car lst) (atom (car lst))) ...)

[CAB]

Another link:
http://www.theswamp.org/index.php?topic=4064.0

[Lee Mac]

Should dotted pairs be considered also?

Code: [Select]

_$ (AT:ListCondense '((1 . 2) (3 (4 5))))
(1 2 3 4 5)
_$ (LM:Flatten '((1 . 2) (3 (4 5))))
(1 2 3 4 5)
_$ (gc:flatlist '((1 . 2) (3 (4 5))))
; error: bad argument type: consp 2

[Lee Mac]

A variant of mine to consider nil as an 'empty atom':

Code: [Select]

(defun LM:Flatten ( l )
  (if (atom l) (list l)
    (append (LM:Flatten (car l)) (if (cdr l) (LM:Flatten (cdr l))))
  )
)


Code: [Select]

_$ (LM:Flatten '((1 . 2) (3 (4 nil 5))))
(1 2 3 4 nil 5)


[alanjt]

[ I hope I'm not stepping on your toes Alan ]

Not at all. I completely forgot about that thread. That's funny that we have almost the method, you just test with atom and I used listp. LoL

[gile]

This one deals with dotted pairs too.

Code: [Select]

(defun gc:flatlist (lst / foo)
  (defun foo (lst acc)
    (if lst
      (foo
(if (listp (cdr lst))
  (cdr lst)
  (list (cdr lst))
)
(if (atom (car lst))
  (cons (car lst) acc)
  (foo (car lst) acc)
)
      )
      acc
    )
  )
  (reverse (foo lst nil))
)

[chlh_jd]

Nice ALL , I suggest do not expand a dotted pair consisting because it has no practical significance .
Here's a function to get all combinations which like a reverse process .

Code: [Select]

(defun powerset (s / foo)
  (defun foo (p s)
    (if s
      (foo (append (mapcar (function (lambda (x)
      (cons (car s) x)
    )
  )
  p
  )
  p
  )
  (cdr s)
      )
      p      
    )
  )
  (reverse (foo (list nil) s))
)


Code: [Select]

(powerset (list 1 2 3))returns

Code: [Select]

((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) nil)

[Jeff H]

Thanks for all the replies,

Is this how you break down the problems???

You can recieve a empty list, atom, or sublist.

Terminating case:
A empty list return nil

Recursive cases:
1. You recieve a atom then add to begining of list then recursivley call function with rest of the list
2. You recieve a sublist then recursivley append the first to the rest of list.

Code: [Select]


(defun LispThingy (lst)
  (if lst
      (cond
        ;; Check to see if atom and if so put it at the
;;the front and recursivley call on rest of the list
((atom (car lst))
     (cons (car lst) (LispThingy (cdr lst)))
)
        ;; If it is a sublist recursivley append first item to
        ;; to recursivley called on rest of the list
((append (LispThingy (car lst)) (LispThingy (cdr lst)))
)
      )
  )
)
At first I was using cons in last recursive case and it just re-built list(I am sure you know that)



Using same breakdown to count the number of atoms

Terminating case:
A empty list return 0

Recursive cases:
1. You recieve a atom then add 1 to recursive call with rest of the list
2. You recieve a sublist then add the recursive call with the first to the recursive call with rest of list.

Code: [Select]


(defun CountAtoms ( lst )
 
    (cond
        ((null lst) 0)
        ((atom (car lst))
   (+ 1 (CountAtoms (cdr lst)))
)

        (T ( + (CountAtoms (car lst))(CountAtoms (cdr lst)))
)
    )   
)

In the link Cab provided I noticed the code looked very similar to this which I picked up same form or layout from here http://art2.ph-freiburg.de/Lisp-Course 

Code: [Select]

(defun flatten ( lst )
    ;;  by Doug Broad
    (cond
        ((null lst) nil)
        ((atom lst) (list lst))
        ((atom (car lst)) (cons (car lst) (Flatten (cdr lst))))
        ((append (Flatten (car lst))(Flatten (cdr lst))))
    )
)

((atom lst) (list lst))
What case is this for?

[Lee Mac]

((atom lst) (list lst))
What case is this for?

Try yours with a dotted pair. 

Another example for the 'CountAtoms' function:

Code: [Select]

(defun CountAtoms ( lst )
  (if (atom lst) 1
    (+ (CountAtoms (car lst)) (if (cdr lst) (CountAtoms (cdr lst)) 0))
  )
)

[VovKa]

Jeff thinks that
(CountAtoms nil) -> 0
Lee thinks that
(CountAtoms nil) -> 1

Who's right?

[Kerry]

since NIL is an atom

(CountAtoms nil) should return 1


unless I misread something

[Lee Mac]

Following the earlier examples, I offer this 'tail recursive' version:

Code: [Select]

(defun CountAtoms ( lst / _iterate )

  (defun _iterate ( lst acc )
    (cond
      ( (null lst) acc )
      ( (atom lst) (1+ acc) )
      ( (atom (car lst)) (_iterate (cdr lst) (1+ acc)) )
      ( (_iterate (cdr lst) (_iterate (car lst) acc) ) )
    )
  )

  (_iterate lst 0)
)
Question: Do all tail recursive functions require an accumulator?

[Jeff H]

Jeff thinks that
(CountAtoms nil) -> 0
Lee thinks that
(CountAtoms nil) -> 1

Who's right?

I am not thinking much and have very little knowledge when it comes to lisp, so I would not assume I fully understand.

With that said I should just go back and edit the OP to say counting all atoms in a given list.
I think that would make the code I posted correct.

[mjfarrell]

Jeff thinks that
(CountAtoms nil) -> 0
Lee thinks that
(CountAtoms nil) -> 1

Who's right?

There is no right or wrong, only ones and zeros, we have achieved a zen state as the answer is both one and zero. 

[JohnK]

<snip>
Question: Do all tail recursive functions require an accumulator?

yes.

[gile]

Question: Do all tail recursive functions require an accumulator?

I'd say: most of the time, yes.

But here's an example of tail recursion without accumulator:

Code: [Select]

(defun some (ele lst)
  (and lst
       (or (equal (car lst) ele)
   (some ele (cdr lst))
       )
  )
)

[Lee Mac]

Thanks gile, that's a good example

I suppose many recursive functions which return a boolean value will be tail-recursive - your example made me think of this one:

Code: [Select]

(defun _member ( x lst )
  (vl-some
    (function
      (lambda ( e )
        (if (listp e) (_member x e) (equal x e))
      )
    )
    lst
  )
)
 

[gile]

I suppose many recursive functions which return a boolean value will be tail-recursive

Not only Boolean returns, this one mimics the native 'member' function:

Code: [Select]

(defun memb (ele lst)
  (if lst
    (if (equal (car lst) ele)
      lst
      (memb ele (cdr lst))
    )
  )
)

[Jeff H]

Is this a decent style or a good way of coding it? Mimicking problem solving and layout from site posted earlier
It is assumed or expected that a list will be the second parameter.

 

Code: [Select]

(defun My-Member (Expression lst)
  (cond
    ((null lst) nil)
    ((equal Expression (car lst)) lst)
    (T (My-Member Expression (cdr lst)))
  )
)   


or is if stament perfered?

[gile]

Is this a decent style or a good way of coding it?

Yes, and probably more readable than nested if statements.

It is assumed or expected that a list will be the second parameter.

With AutoLISP, the arguments order doesn't matter more than make the code more readable (or similar to built-in functions).
For example, most AutoLISP higher order functions (mapcar, vl-some, ...) require the function argument as first argument but vl-sort take it as last argument.

The choice of arguments order is more important in F# due to the pipelining ability (as List.map or List.exists, List.sortBy or List.sortWith requires the list as last argument).

[Peter Jamtgaard]

I noticed this thread over at augi lisp forum,

this was what I came up with...

I figure one of you guys must have already come up with this,

but if you haven't...

Peter

Code:

Code: [Select]

(defun RecurseList (lstSublist)
 (if (= (type lstSublist) 'LIST)
  (apply 'append (mapcar 'recurselist lstSublist))
  (list lstSublist) 
 )
)

(recurselist '((1 2 (3 4)) (5 (6 7)) "A" nil ((8 nil 9 (10 (11)))) (((A) B) C) (D (E (F (G))))))

returns

'(1 2 3 4 5 6 7 "A" nil 8 nil 9 10 11 A B C D E F G)

Recursion is really mind bending for me 

Comments?

[Lee Mac]

Hi Peter,

Nice code but you'll have trouble with mapcar when faced with dotted pairs

Lee

[Peter Jamtgaard]

It is definitely not as elegant, and one of the reasons I tend to avoid using dotted pairs in my code in lists of sublists

Any suggestions on a better way to determine if a dotted pair is a list would be interesting.

When ever I come up with any new code like that I can depend on the
members of the swamp to let some of the hot air out of my ego...

Nasty dotted pairs...   

So

Code: [Select]

(defun DottedPairToList (dprItem)
 (if (and (= (type dprItem) 'LIST)
          (cdr dprItem)
          (/= (type (cdr dprItem)) 'LIST)
         
     )
  (list (car dprItem) (cdr dprItem))
  dprItem
 )
)

(defun RecurseList (lstSublist)
 (if (= (type lstSublist) 'LIST)
  (apply 'append (mapcar 'recurselist (dottedpairtolist lstSublist)))
  (list lstSublist) 
 )
)


Code: [Select]

(recurselist '((1 2 (3 4)) (5 (6 . 7)) "A" nil ((8 nil 9 (10 (11)))) (((A) B) C) (D (E (F (G . H))))))
 returns
'(1 2 3 4 5 6 7 "A" nil 8 nil 9 10 11 A B C D E F G H)


[Lee Mac]

Any suggestions on a better way to determine if a dotted pair is a list would be interesting.

Maybe?

Code: [Select]

(defun DottedPairToList ( dprItem )
  (if (vl-list-length dprItem)
    dprItem
    (list (car dprItem) (cdr dprItem))
  )
)

[Peter Jamtgaard]

Or maybe

Code: [Select]


(defun RecurseList (lstSublist)
 (if (= (type lstSublist) 'LIST)
  (apply 'append
   (mapcar 'recurselist
    (if (cdr lstSublist)
     (list (car lstSublist) (cdr lstSublist))
     lstSublist
    )
   )
  )
  (list lstSublist)  
 )
)
Definitely not as elegant but think that is as short as this method can go

[Peter Jamtgaard]

I like that vl-list-length function solution.

[JohnK]

Can i ask how are you guys defining "tail recursive" functions. How i learned `tail recursion' there are no instructions after the recursive call ("snapshots in time" if you will) on the stack. ...I am severely out of practice when it comes to lisp so i could be reading it wrong but some of those functions labeled as `tail recursive' are not by my knowledge.

[gile]

Hi se7en,

It's quite difficult for me to explain this in English but I *do* think the functions I posted are tail recursive.

A way to see if a LISP recursive function is tail recursive is to trace the function. If the last call on the stack returns the final result, then the function is tail recursive.

Example with the famous factorial function:

fact1 is not tail recursive:

Code: [Select]

(defun fact1 (n)
  (if (<= n 1)
    1
    (* n (fact1 (1- n)))
  )
)
fact2 calls f which is tail recursive (with an accumulator):

Code: [Select]

(defun fact2 (n / f)
  (defun f (n a)
    (if (<= n 1)
      a
      (f (1- n) (* n a))
    )
  )
  (f n 1)
)
Tracing both: (trace fact1 f) and running: (fact1 5) (fact2 5), the vlide trace window displays:

Code: [Select]

Saisie (FACT1 5)
  Saisie (FACT1 4)
    Saisie (FACT1 3)
      Saisie (FACT1 2)
        Saisie (FACT1 1)
        Résultat:  1
      Résultat:  2
    Résultat:  6
  Résultat:  24
Résultat:  120
Saisie (F 5 1)
  Saisie (F 4 5)
    Saisie (F 3 20)
      Saisie (F 2 60)
        Saisie (F 1 120)
        Résultat:  120
      Résultat:  120
    Résultat:  120
  Résultat:  120
Résultat:  120
Doing the same thing with the memb function (wich is tail recursive without accumulator) and the trunc function (the complementary function which is not tail recursive:

Code: [Select]

(defun memb (ele lst)
  (if lst
    (if (equal (car lst) ele)
      lst
      (memb ele (cdr lst))
    )
  )
)

(defun trunc (ele lst)
  (if lst
    (if (equal (car lst) ele)
      nil
      (cons (car lst) (trunc ele (cdr lst)))
    )
  )
)
Tracing both (trace memb trunc) and runing (memb 2 '(0 1 2 3)) (trunc 2 '(0 1 2 3)):

Code: [Select]

Saisie (MEMB 2 (0 1 2 3))
  Saisie (MEMB 2 (1 2 3))
    Saisie (MEMB 2 (2 3))
    Résultat:  (2 3)
  Résultat:  (2 3)
Résultat:  (2 3)
Saisie (TRUNC 2 (0 1 2 3))
  Saisie (TRUNC 2 (1 2 3))
    Saisie (TRUNC 2 (2 3))
    Résultat:  nil
  Résultat:  (1)
Résultat:  (0 1)
In both examples, with non tail recursive functions (fact1 and trunc) the last call calls the recursive function within another statement: (* n (fact1 (1- n))) and (cons (car lst) (trunc ele (cdr lst))) so that the final result can't be solved until unstacking.
With the tail recusive functions (f and memb) the last call directly calls the function: (f (1- n) (* n a)) and (memb ele (cdr lst)) and the final result is returned soon the head of the stack.

If you're no more comfortable with LISP, you can try with F# (which optimises the tail recursion).
Here're F# traductions of the memb and trunc functions, you can try here if you do not have F# (VS 2010) installed.

Code: [Select]

let rec memb ele lst =
    match lst with
    | [] -> []
    | h::t when h = ele -> lst
    | _ -> memb ele lst.Tail
   
let rec trunc ele lst =
    match lst with
    | [] -> []
    | h::t when h = ele -> []
    | _ -> lst.Head :: trunc ele lst.Tail
Then, try:
memb 199999 [0 .. 200000]
and
trunc 199999 [0 .. 200000]

The return in F# interactive should be:

Code: [Select]

> memb 199999 [0 .. 200000];;
val it : int list = [199999; 200000]

> trunc 199999 [0 .. 200000];;
Session termination detected. Press Enter to restart.

Process is terminated due to StackOverflowException.

[Lee Mac]

The way I understood 'tail-recursive' functions was that when a result was reached (perhaps n levels deep), that same result would be carried back (unmodified) through the recursive calls and be returned - hence, as you say, no expressions are to be evaluated following the return of the recursive call.

I think it is better understood from a 'trace' of the function (using gile's 'memb' function as an example):

Code: [Select]

Entering (MEMB 3 (0 1 2 3 4 5))
  Entering (MEMB 3 (1 2 3 4 5))
    Entering (MEMB 3 (2 3 4 5))
      Entering (MEMB 3 (3 4 5))
      Result:  (3 4 5)
    Result:  (3 4 5)
  Result:  (3 4 5)
Result:  (3 4 5)

The result (3 4 5) being identical for each return of the recursive call.

EDIT: Gile beat me to it

[VovKa]

How i learned `tail recursion' there are no instructions after the recursive call

how i thought 'tail recursion' there are no instructions before the recursive call.
now i'm stuck

[Lee Mac]

How i learned `tail recursion' there are no instructions after the recursive call

how i thought 'tail recursion' there are no instructions before the recursive call.
now i'm stuck

But LISP is evaluated 'inside-out' so I think you both mean the same thing - i.e. the expressions appear before the recursive call, but are evaluated using the return of the recursive call.

Am I right?

[JohnK]

Thanks gile. I will have to wait untill i get back at work (back to a computer with AutoCAD) to study the code.


My `after' statement was refering to the "backtrace". in that, there wouldnt be one with `tail recusion'.

For the record; This is how i learned to do `tail recursion'. I think i tried to start a discussion on this at one time or another...huh.

Code: [Select]

(map-car-iter
  (lambda (x) (+ x 1))
             '(1 2 3) )

(defun map-car-iter ( proc lst)
   (map-iter '() proc lst) )

(defun map-iter (sofar proc lis)
   (if (null lis)
       (reverse sofar)
       (map-iter (cons (proc (car lis))
                       sofar)
                 proc
                 (cdr lis))) )

[gile]

My `after' statement was refering to the "backtrace". in that, there wouldnt be one with `tail recusion'.

Even your 'map-iter':

Code: [Select]

Saisie (MAP-ITER nil #<USUBR @000000002b88fe80 -lambda-> (1 2 3))
  Saisie (MAP-ITER (2) #<USUBR @000000002b88fe80 -lambda-> (2 3))
    Saisie (MAP-ITER (3 2) #<USUBR @000000002b88fe80 -lambda-> (3))
      Saisie (MAP-ITER (4 3 2) #<USUBR @000000002b88fe80 -lambda-> nil)
      Résultat:  (2 3 4)
    Résultat:  (2 3 4)
  Résultat:  (2 3 4)
Résultat:  (2 3 4)

[jmcshane]

Code: [Select]

(defun My-Member ......


Classic!!!