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))
  )
)